On k-column sparse packing programs

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

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    24 Citaten (Scopus)

    Samenvatting

    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.
    Originele taal-2Engels
    TitelInteger Programming and Combinatorial Optimization (14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings)
    RedacteurenF. Eisenbrand, F.B. Shepherd
    Plaats van productieBerlin
    UitgeverijSpringer
    Pagina's369-382
    ISBN van geprinte versie978-3-642-13035-9
    DOI's
    StatusGepubliceerd - 2010

    Publicatie series

    NaamLecture Notes in Computer Science
    Volume6080
    ISSN van geprinte versie0302-9743

    Vingerafdruk

    Duik in de onderzoeksthema's van 'On k-column sparse packing programs'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit