  


An improved approximation algorithm for the covering 01 integer program
Yotaro Takazawa(takazawa.y.abm.titech.ac.jp) Abstract: We present an improved approximation algorithm for the covering 01 integer program (CIP), a wellknown problem as a natural generalization of the set cover problem. Our algorithm uses a primaldual algorithm for CIP by Fujito (2004) as a subroutine and achieves an approximation ratio of (f (f1)/m) when m is greater than or equal to 2, where m is the number of the constraints and f is the maximum number of nonzero entries in the constraints. In addition, when m=1 our algorithm can be regarded as a PTAS. These results improve the previously known approximation ratio f. Keywords: Approximation algorithms, Covering integer program, Primaldual method Category 1: Combinatorial Optimization (Approximation Algorithms ) Citation: to appear in department of Industrial Engineering and Economics Working Paper, Tokyo Institute of Technology. Download: [PDF] Entry Submitted: 08/06/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  