On k-column sparse packing programs

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

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

    25 Citations (Scopus)


    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
    ISBN (Print)978-3-642-13035-9
    Publication statusPublished - 2010

    Publication series

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


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

    Cite this