Optimization Online


Linear-time approximation algorithms for minimum subset sum and subset sum

Liliana Grigoriu (liliana.grigoriu***at***gmail.com)

Abstract: We present a linear-time approximation algorithm for minimum subset sum, which has better worst-case approximation factor (6/5) than previous linear-time 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 linear-time approximation algorithms for subset sum with worst-case approximation factors of k/(k+1) assuming that k is constant.

Keywords: subset sum; minimum subset sum; linear-time approximation; approximation algorithms

Category 1: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 11/03/2016
Entry Accepted: 11/03/2016
Entry Last Modified: 07/16/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society