@techreport{TD:101509,
	att_abstract={{In this paper, we introduce a natural generalization of Weighted Set Cover and Maximum Coverage, called Size-Constrained Weighted Set Cover. The input is a collection of n elements, a collection of weighted sets over the elements, a size constraint k, and a minimum coverage fraction s; the output is a sub-collection of up to k sets whose union contains at least sn elements and whose sum of weights is minimal. We prove the hardness of approximation of this problem, and we present efficient approximation algorithms with provable quality guarantees that are the best possible. In many applications, the elements are data records with multiple attributes, and the set collection to choose from is derived from the various combinations (patterns) of attribute values. We provide optimization techniques for this special case. Finally, we experimentally demonstrate the effectiveness and efficiency of our solutions}},
	att_authors={ds8961},
	att_categories={C_NSS.2, C_CCF.1},
	att_copyright={{IEEE}},
	att_copyright_notice={{This version of the work is reprinted here with permission of IEEE for your personal use. Not for redistribution. The definitive version was published in 2014. {{, 2015-04-13}}
}},
	att_donotupload={},
	att_private={false},
	att_projects={},
	att_tags={},
	att_techdoc={true},
	att_techdoc_key={TD:101509},
	att_url={http://web1.research.att.com:81/techdocs_downloads/TD:101509_DS1_2014-10-21T22:05:28.890Z.pdf},
	author={Divesh Srivastava and Lukasz Golab and Flip Korn and Feng Li and Barna Saha},
	institution={{IEEE International Conference on Data Engineering}},
	month={April},
	title={{Size-Constrained Weighted Set Cover}},
	year=2015,
}