2-Catalog segmentation problem

Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna

Research output: Contribution to conferencePaper

Abstract

The 2-catalog segmentation problem is investigated. The problem is stated as: given a set I of n items and a family of p subsets of I, find two subsets (C1, C2) of I bounded by the catalog size r and the sum (2) is maximized. In general, only a trivial 0.5 approximation algorithm is known. An improvement upon this factor is made under the assumption that |I| is bounded by 2r.

Original languageEnglish (US)
PagesS897-S898
StatePublished - 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of '2-Catalog segmentation problem'. Together they form a unique fingerprint.

  • Cite this

    Dodis, Y., Guruswami, V., & Khanna, S. (1999). 2-Catalog segmentation problem. S897-S898. Paper presented at Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, .