Segmentation problems

被引：56

作者：

Kleinberg, J

Papadimitriou, C

Raghavan, P

机构：

[1] Cornell Univ, Dept Comp Sci, Ithaca, NY 14853 USA

[2] Univ Calif Berkeley, Berkeley, CA 94720 USA

[3] Verity, Sunnyvale, CA 94089 USA

来源：

JOURNAL OF THE ACM | 2004年 / 51卷 / 02期

关键词：

clustering; data mining; approximation algorithms; market segmentation;

D O I：

10.1145/972639.972644

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：263 / 280

页数：18

共 18 条

[1]

Agrawal R., 1993, SIGMOD Record, V22, P207, DOI 10.1145/170036.170072

[2] On two segmentation problems [J].

Alon, N ;

Sudakov, B .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 33 (01) :173-184

[3]

[Anonymous], 1981, Algorithms for Clustering Data

[4]

[Anonymous], P INT C KNOWL DISC D

[5]

Arora S., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P284, DOI 10.1145/225058.225140

[6]

Berman O, 1995, FACILITY LOCATION SU

[7]

BERN M, 1996, APPROXIMATIN ALGORIT

[8]

COGGINS J, 1983, TIME WARPS STRING ED

[9] LOCATION OF BANK ACCOUNTS TO OPTIMIZE FLOAT - ANALYTIC STUDY OF EXACT AND APPROXIMATE ALGORITHMS [J].

CORNUEJOLS, G ;

FISHER, ML ;

NEMHAUSER, GL .

MANAGEMENT SCIENCE, 1977, 23 (08) :789-810

[10]

FEDER T, 1988, P ACM S THEORY COMP

← 1 2 →