  


Lineartime approximation algorithms for minimum subset sum and subset sum
Liliana Grigoriu (liliana.grigoriugmail.com) Abstract: We present a lineartime approximation algorithm for minimum subset sum, which has better worstcase approximation factor (6/5) than previous lineartime algorithms for this problem. We also present a generalization of the scheme used to derive the algorithm, which can be used to obtain algorithms with approximation ratios of (k+1)/k. In addition, we present a family of lineartime approximation algorithms for subset sum with worstcase approximation factors of k/(k+1) assuming that k is constant. Keywords: subset sum; minimum subset sum; lineartime approximation; approximation algorithms Category 1: Combinatorial Optimization (Approximation Algorithms ) Citation: Download: [PDF] Entry Submitted: 11/03/2016 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  