On k-column sparse packing programs

N. Bansal, N. Korula, V. Nagarajan, A. Srinivasan

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    23 Citations (Scopus)

    Abstract

    We consider the class of packing integer programs (PIPs) that are column sparse, where there is a specified upper bound k on the number of constraints that each variable appears in. We give an improved (ek¿+¿o(k))-approximation algorithm for k-column sparse PIPs. Our algorithm is based on a linear programming relaxation, and involves randomized rounding combined with alteration. We also show that the integrality gap of our LP relaxation is at least 2k¿-¿1; it is known that even special cases of k-column sparse PIPs are formula -hard to approximate. We generalize our result to the case of maximizing monotone submodular functions over k-column sparse packing constraints, and obtain an formula-approximation algorithm. In obtaining this result, we prove a new property of submodular functions that generalizes the fractionally subadditive property, which might be of independent interest.
    Original languageEnglish
    Title of host publicationInteger Programming and Combinatorial Optimization (14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings)
    EditorsF. Eisenbrand, F.B. Shepherd
    Place of PublicationBerlin
    PublisherSpringer
    Pages369-382
    ISBN (Print)978-3-642-13035-9
    DOIs
    Publication statusPublished - 2010

    Publication series

    NameLecture Notes in Computer Science
    Volume6080
    ISSN (Print)0302-9743

    Fingerprint Dive into the research topics of 'On k-column sparse packing programs'. Together they form a unique fingerprint.

    Cite this