TY  - JOUR
T1  - Segmentation problems.
JF  - Journal of the ACM
A1  - Kleinberg, Jon
LA  - English
UL  - https://tuklas.up.edu.ph/Record/UP-99796217608727423
AB  - 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.
KW  - Theory of computation.
KW  - Analysis of algorithms and problem complexity.
KW  - Nonnumerical algorithms and problems.
KW  - Information systems.
KW  - Database management.
KW  - Database applications.
KW  - Data mining.
KW  - Algorithms.
KW  - Theory.
ER  -