Name
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1145/972639.972644 | J. ACM |
Keywords | DocType | Volume |
data mining,classical optimization problem,present approximation algorithm,market segmentation,cost vector,catalog segmentation problem,corresponding segmentation problem,hypercube segmentation problem,optimization problem,overall cost,certain aspect,approximation algorithms,segmentation problem,clustering | Journal | 51 |
Issue | Citations | PageRank |
2 | 18 | 1.33 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jon Kleinberg | 1 | 22707 | 2358.90 |
| Christos H. Papadimitriou | 2 | 16671 | 3192.54 |
| Prabhakar Raghavan | 3 | 13351 | 2776.61 |