Presentation	2001/7/9 A Modified Greedy Algorithm for the Set Cover Problem with Weights 1 and 2 Toshihiro Fujito, Tsuyoshi Okumura,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	The set cover problem is that of computing, given a family of weighted subsets of a base set U, a minimum weight subfamily F′ such that every element of U is covered by some subset in F′. The κ-set cover problem is a variant in which every subset is of size bounded by κ. It has been long known that the problem can be approximated within a factor of H(κ)=Σ^κ_(1/i) by the greedy heuristic, but no better bound has been shown except for the case of unweighted subsets. In this paper we consider approximation of a restricted version of the weighted κ-set cover problem, as a first step towards better approximation of general κ-set cover problem, where subset costs are limited to either 1 or 2.It will be shown, via LP duality, that improved approximation bounds of H(3)-1/6 for 3-set cover and H(κ)-1/12 for κ-set cover can be attained, when the greedy heuristic is suitably modified for this case.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	approximation algorithm / set cover / greedy heuristic
Paper #	COMP2001-24
Date of Issue

Conference Information
Committee	COMP
Conference Date	2001/7/9(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	A Modified Greedy Algorithm for the Set Cover Problem with Weights 1 and 2
Sub Title (in English)
Keyword(1)	approximation algorithm
Keyword(2)	set cover
Keyword(3)	greedy heuristic
1st Author's Name	Toshihiro Fujito
1st Author's Affiliation	Department of Electronics, Nagoya University()
2nd Author's Name	Tsuyoshi Okumura
2nd Author's Affiliation	Department of Electronics, Nagoya University
Date	2001/7/9
Paper #	COMP2001-24
Volume (vol)	vol.101
Number (no)	184
Page	pp.pp.-
#Pages	8
Date of Issue