NDLI: On Combinatorial Approximation of Covering 0-1 Integer Programs and Partial Set Cover

Content Provider	Springer Nature Link
Author	Fujito, Toshihiro
Copyright Year	2004
Abstract	The problems dealt with in this paper are generalizations of the set cover problem, min{cx \| Ax ≥ b, x ∈{0,1}$^{n}$}, where c ∈ Q$_{+}$$^{n}$, A ∈ {0,1}$^{m × n}$, b ∈ 1. The covering 0-1 integer program is the one, in this formulation, with arbitrary nonnegative entries of A and b, while the partial set cover problem requires only m–K constrains (or more) in Ax ≥ b to be satisfied when integer K is additionall specified. While many approximation algorithms have been recently developed for these problems and their special cases, using computationally rather expensive (albeit polynomial) LP-rounding (or SDP-rounding), we present a more efficient purely combinatorial algorithm and investigate its approximation capability for them. It will be shown that, when compared with the best performance known today and obtained by rounding methods, although its performance comes short in some special cases, it is at least equally good in general, extends for partial vertex cover, and improves for weighted multicover, partial set cover, and further generalizations.
Starting Page	439
Ending Page	452
Page Count	14
File Format	PDF
ISSN	13826905
Journal	Journal of Combinatorial Optimization
Volume Number	8
Issue Number	4
e-ISSN	15732886
Language	English
Publisher	Kluwer Academic Publishers
Publisher Date	2004-01-01
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Theory of Computation Mathematical Modeling and Industrial Mathematics Combinatorics Convex and Discrete Geometry Optimization Operation Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Control and Optimization Discrete Mathematics and Combinatorics Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An approximation algorithm for the partial vertex cover problem in hypergraphs

Approximation algorithms for minimum weight partial connected set cover problem

Requiring Connectivity in the Set Covering Problem

An approximation algorithm for maximum weight budgeted connected set cover

Tight approximation bounds for combinatorial frugal coverage algorithms

Benders decomposition for set covering problems : Almost satisfying the consecutive ones property

On nonlinear multi-covering problems

Approximation algorithm for partial positive influence problem in social network

On Some Polyhedra Covering Problems

On Combinatorial Approximation of Covering 0-1 Integer Programs and Partial Set Cover

Similar Documents

An approximation algorithm for the partial vertex cover problem in hypergraphs

Approximation algorithms for minimum weight partial connected set cover problem

Requiring Connectivity in the Set Covering Problem

An approximation algorithm for maximum weight budgeted connected set cover

Tight approximation bounds for combinatorial frugal coverage algorithms

Benders decomposition for set covering problems : Almost satisfying the consecutive ones property

On nonlinear multi-covering problems

Approximation algorithm for partial positive influence problem in social network

On Some Polyhedra Covering Problems

On Combinatorial Approximation of Covering 0-1 Integer Programs and Partial Set Cover