A Subquadratic Approximation Scheme for Partition

The Subset Sum problem is one of the most fundamental problem in theoretical computer science. One is given a set S of n integers and an integer t. The problem is to determine if there exists a subset of S with total sum equal exactly t.

The Partition is a special case of Subset Sum when one is given a set S of integers and needs to partition it into two sets of equal total sum. Both of these problems are NP-hard and admit an approximation scheme running in  time. This algorithm is conditionally tight for Subset Sum. On ACM-SIAM Symposium on Discrete Algorithms we will present an approximation algorithm in  time for Partition. We cordially invite you to attend our presentation 6th January 2019 in San Diego.

Marcin Mucha, Karol Węgrzycki, Michał Włodarczyk

Leave a Reply

Your email address will not be published. Required fields are marked *