@inproceedings{a0d4f1307e794d2e8b278df80df9f29e,

title = "On k-column sparse packing programs",

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.",

author = "N. Bansal and N. Korula and V. Nagarajan and A. Srinivasan",

year = "2010",

doi = "10.1007/978-3-642-13036-6_28",

language = "English",

isbn = "978-3-642-13035-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "369--382",

editor = "F. Eisenbrand and F.B. Shepherd",

booktitle = "Integer Programming and Combinatorial Optimization (14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings)",

address = "Germany",

}