Presentation	1997/10/31 Maximum Agreement Problem for Word Association Patterns Hiroki Arimura, Atsushi Wataki, Shinichi Shimozono,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	We consider the problem to find a pattern over strings that maximizes the precision of classifying the given positive- and negative-labeled strings. We introduce a notion of patterns for specifying associations between two strings, and present an efficient algorithm that finds a pattern with the best precision and runs in O(n^2) time and with O(kn) space. Furthermore, we show that if patterns are extended to associations over arbitrary many strings then the problem is not approximable within arbitrary small error ratio in polynomial time unless P=NP.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	data mining / maximum agreement problem / polynomial-time approximation
Paper #	COMP97-57
Date of Issue

Conference Information
Committee	COMP
Conference Date	1997/10/31(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Maximum Agreement Problem for Word Association Patterns
Sub Title (in English)
Keyword(1)	data mining
Keyword(2)	maximum agreement problem
Keyword(3)	polynomial-time approximation
1st Author's Name	Hiroki Arimura
1st Author's Affiliation	Dept. of Informatics, Kyushu University()
2nd Author's Name	Atsushi Wataki
2nd Author's Affiliation	Dept. of Informatics, Kyushu University
3rd Author's Name	Shinichi Shimozono
3rd Author's Affiliation	Dept. of Artificial Intelligence, Kyushu Institute of Technology
Date	1997/10/31
Paper #	COMP97-57
Volume (vol)	vol.97
Number (no)	356
Page	pp.pp.-
#Pages	8
Date of Issue