Segmentation problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Segmentation problems

Full text

Pdf (1.39 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 473 - 482

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Jon Kleinberg	Department of Computer Science, Cornell University, Ithaca, NY
Christos Papadimitriou	Computer Science Division, Soda Hall, UC Berkeley, CA
Prabhakar Raghavan	IBM Almaden Research Center, 650 Harry Road, San Jose, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 45, Citation Count: 23

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276860 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, ACM SIGMOD Record, v.22 n.2, p.207-216, June 1, 1993
	2	Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225140]
	3	M. Avriel. NonlinearProgramming: Analysis and Methods. Prentice-HaU, 1976.
	4	O. Berman, M.J. Hodgson, D. Krass. "Flow-interception problems" in Facility Location: A Survey of Applications and Methods, Z. Drezner, Ed., Springer 1995.
	5	Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	6	M. J. Berry, G. Linoff. Data Mining Techniques. John- Wiley, 1997.
	7	Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.255-264, May 11-15, 1997, Tucson, Arizona, United States
	8	Ming-Syan Chen , Jiawei Han , Philip S. Yu, Data Mining: An Overview from a Database Perspective, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.866-883, December 1996 [doi>10.1109/69.553155]
	9	J.M. Coggins. "Dissimilarity measures for clustering strings" in 7~me B~trps, String Edits, and Macromolecules: The Theory attd Practice of Sequence Comparison, D. Sankoff and J.S.B. Kruskal, Eds., Addison- Wesley, 1983.
	10	G. Comuejols, M. Fisher, G. Nemhauser. "Location of Bank Accounts to Optimize Float,' Management Science, 23(1977), pp. 789-810.
	11	G. B. Dantzig. Linear programming and Extensions. Princeton Unix: Press, 1963.
	12	Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
	13	T. Gonzalez. "Clustering to minimize the maximum inter-cluster distance, Theoretical Computer Science, 38(1985), pp. 293-306.
	14	Dimitrios Gunopulos , Heikki Mannila , Roni Khardon , Hannu Toivonen, Data mining, hypergraph transversals, and machine learning (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.209-216, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263684]
	15	Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	16	M. Kearns, Y. Mansour, A. Ng. '~n informationtheoretic analysis of hard and soft assignment methods for clustering,' Proc. 13th Conference on Uncertainty in Artificial InteUigence, 1997.
	17	B. Liu and W. Hsu. "Post-analysis of learned roles" Proc. AAM, pp. 828-834, 1996.
	18	B.M. Masand and G. Piatetsky-Shapiro."A comparison of approaches for maximizing business payoff of prediction models". Proc. Knowledge Discovery and Data Mining, 195-201, 1996.
	19	G. Nemhauser, L. Wolse3; M. Fisher. '%n analysis of the approximations for maximizing submodular set functions;' Mathematical Programming, 14(1978), pp. 265-294.
	20	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	21	O. Piatetsky-Schapiro, C. J. Matheus. "The interestingness of deviations;' Proc. Knowledge Discover), attd Data Mining,, pp. 25-36, 1994.
	22	David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
	23	Avi Silberschatz , Alexander Tuzhilin, What Makes Patterns Interesting in Knowledge Discovery Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.970-974, December 1996 [doi>10.1109/69.553165]
	24	P. Smyth, R. M. Goodman. "Rule induction using information theory" Proc. Knowledge Discovery andData Mining, 1991.

CITED BY 23

	Petros Drineas , Iordanis Kerenidis , Prabhakar Raghavan, Competitive recommendation systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece
	Yevgeniy Dodis , Venkatesan Guruswami , Sanjeev Khanna, The 2-catalog segmentation problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.897-898, January 17-19, 1999, Baltimore, Maryland, United States
	Rafail Ostrovsky , Yuval Rabani, Polynomial-time approximation schemes for geometric min-sum median clustering, Journal of the ACM (JACM), v.49 n.2, p.139-156, March 2002
	P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
	W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon , Yuval Rabani, Approximation schemes for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Martin Ester , Rong Ge , Wen Jin , Zengjian Hu, A microeconomic data mining problem: customer-oriented catalog segmentation, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	Moses Charikar , Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, On targeting Markov segments, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.99-108, May 01-04, 1999, Atlanta, Georgia, United States
	Nina Mishra , Dana Ron , Ram Swaminathan, A New Conceptual Clustering Framework, Machine Learning, v.56 n.1-3, p.115-151
	Hanson Zhou , David Woodruff, Clustering via matrix powering, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Nir Ailon , Bernard Chazelle , Seshadhri Comandur , Ding Liu, Self-improving algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.261-270, January 22-26, 2006, Miami, Florida
	Omid Madani , Dennis DeCoste, Contextual recommender problems [extended abstract], Proceedings of the 1st international workshop on Utility-based data mining, p.86-89, August 21-21, 2005, Chicago, Illinois
	Rakesh Agrawal , Ralf Rantzau , Evimaria Terzi, Context-sensitive ranking, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Ali Amiri, Customer-oriented catalog segmentation: effective solution approaches, Decision Support Systems, v.42 n.3, p.1860-1871, December 2006
	Jianying Hu , Aleksandra Mojsilovic, High-utility pattern mining: A method for discovery of high-utility item sets, Pattern Recognition, v.40 n.11, p.3317-3324, November, 2007
	Cuiping Li , Anthony K. H. Tung , Wen Jin , Martin Ester, On dominating your neighborhood profitably, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Cuiping Li , Beng Chin Ooi , Anthony K. H. Tung , Shan Wang, DADA: a data cube for dominant relationship analysis, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, A Microeconomic View of Data Mining, Data Mining and Knowledge Discovery, v.2 n.4, p.311-324, December 1998
	Themis Palpanas , Nick Koudas , Alberto Mendelzon, On space constrained set selection problems, Data & Knowledge Engineering, v.67 n.1, p.200-218, October, 2008
	Zhenjie Zhang , Laks V. S. Lakshmanan , Anthony K. H. Tung, On domination game analysis for microeconomic data mining, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.4, p.1-27, January 2009
	Xiujuan Xu , Yu Liu , Zhe Wang , Chunguang Zhou , Yanchun Liang, Catalog segmentation with double constraints in business, Pattern Recognition Letters, v.30 n.4, p.440-448, March, 2009
	Bill Andreopoulos , Aijun An , Xiaogang Wang , Dirk Labudde, Efficient layered density-based clustering of categorical data, Journal of Biomedical Informatics, v.42 n.2, p.365-376, April, 2009