Approximate Min-Sum Subset Convolution

2024/04/17 by Mihail Stoian, Stoian, Mihail · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Approximation and Integration

paper · pdf · doi:10.48550/arxiv.2404.11364

openalex publication_date 2024/04/17 · openalex created_date 2024/04/19 · openalex updated_date 2026/07/28

Abstract

Exponential-time approximation has recently gained attention as a practical way to deal with the bitter NP-hardness of well-known optimization problems. We study for the first time the (1 + ε)-approximate min-sum subset convolution. This enables exponential-time (1 + ε)-approximation schemes for problems such as minimum-cost k-coloring, the prize-collecting Steiner tree, and many others in computational biology. Technically, we present both a weakly- and strongly-polynomial approximation algorithm for this convolution, running in time \widetilde O(2ⁿ log M / ε) and \widetilde O(2^(3n)/(2) / √(ε)), respectively. Our work revives research on tropical subset convolutions after nearly two decades.

Cited by

• A pumping-like lemma for languages over infinite alphabets

Related

• A Fine-Grained Perspective on Approximating Subset Sum and Partition
• Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset\n Sum
• The problematic nature of potentially polynomial-time algorithms solving the subset-sum problem
• Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
• Exponential-Time Approximation of Hard Problems