### 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 (C_{1}, C_{2}) 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 language | English (US) |
---|---|

Pages | S897-S898 |

State | Published - 1999 |

Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |

### Other

Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | Baltimore, MD, USA |

Period | 1/17/99 → 1/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, .