2016/07/27 by Cédric Bentz, Bentz, Cédric, Pierre Le Bodic +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1607.07950
openalex publication_date 2016/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Pruhs and Woeginger prove the existence of FPTAS's for a general class of\nminimization and maximization subset selection problems. Without losing\ngenerality from the original framework, we prove how better asymptotic\nworst-case running times can be achieved if a \ρ-approximation algorithm is\navailable, and in particular we obtain matching running times between\nmaximization and minimization subset selection problems. We directly apply this\nresult to the Minimum Knapsack Problem, for which the original framework yields\nan FPTAS with running time O(n5/\ε), where \ε is the required\naccuracy and n is the number of items, and obtain an FPTAS with running time\nO(n3/\ε), thus improving the running time by a quadratic factor in the\nworst case.\n