Segmentation problems
- 1 March 2004
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 51 (2) , 263-280
- https://doi.org/10.1145/972639.972644
Abstract
We study a novel genre of optimization problems, which we call segmentation problems , motivated in part by certain aspects of clustering and data mining. For any classical optimization problem, the corresponding segmentation problem seeks to partition a set of cost vectors into several segments , so that the overall cost is optimized. We focus on two natural and interesting (but MAXSNP-complete) problems in this class, the hypercube segmentation problem and the catalog segmentation problem, and present approximation algorithms for them. We also present a general greedy scheme, which can be specialized to approximate any segmentation problem.Keywords
This publication has 10 references indexed in Scilit:
- On Two Segmentation ProblemsJournal of Algorithms, 1999
- A Microeconomic View of Data MiningData Mining and Knowledge Discovery, 1998
- Approximation algorithms for facility location problems (extended abstract)Published by Association for Computing Machinery (ACM) ,1997
- What makes patterns interesting in knowledge discovery systemsIEEE Transactions on Knowledge and Data Engineering, 1996
- Flow-Interception ProblemsPublished by Springer Nature ,1995
- Polynomial time approximation schemes for dense instances of NP-hard problemsPublished by Association for Computing Machinery (ACM) ,1995
- Mining association rules between sets of items in large databasesPublished by Association for Computing Machinery (ACM) ,1993
- Optimal algorithms for approximate clusteringPublished by Association for Computing Machinery (ACM) ,1988
- Clustering to minimize the maximum intercluster distanceTheoretical Computer Science, 1985
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978