@inbook {17635,
	title = {On k-Column Sparse Packing Programs},
	booktitle = {Integer Programming and Combinatorial OptimizationInteger Programming and Combinatorial Optimization},
	series = {Lecture Notes in Computer Science},
	volume = {6080},
	year = {2010},
	month = {2010///},
	pages = {369 - 382},
	publisher = {Springer Berlin / Heidelberg},
	organization = {Springer Berlin / Heidelberg},
	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 (klogk)-hard to approximate.We generalize our result to the case of maximizing monotone submodular functions over k-column sparse packing constraints, and obtain an e2ke-1+o(k) -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.
},
	isbn = {978-3-642-13035-9},
	url = {http://dx.doi.org/10.1007/978-3-642-13036-6_28},
	author = {Bansal,Nikhil and Korula,Nitish and Nagarajan,Viswanath and Srinivasan, Aravind},
	editor = {Eisenbrand,Friedrich and Shepherd,F.}
}
