Approximation schemes for a class of subset selection problems

DOI10.1016/j.tcs.2007.03.006zbMath1119.90077OpenAlexW2165102171MaRDI QIDQ2381527

Kirk R. Pruhs, Gerhard J. Woeginger

Publication date: 18 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/approximation-schemes-for-a-class-of-subset-selection-problems(92dc9a9b-9a37-4e4c-83ef-4c2b32464846).html

zbMATH Keywords

combinatorial optimizationapproximation algorithmscheduling theoryapproximation schemeFPTASworst case analysispseudo-polynomial algorithm

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items

The knapsack problem with special neighbor constraints, Approximation schemes for subset-sums ratio problems, Online Throughput Maximization on Unrelated Machines: Commitment is No Burden, Inverse median location problems with variable coordinates, General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems, Inverse 1-median problem on trees under weighted Hamming distance, Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs, Unnamed Item, Approximation of knapsack problems with conflict and forcing graphs, Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date, A comparative analysis of two matheuristics by means of merged local optima networks, Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth, Online multistage subset maximization problems, Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width, Strongly polynomial FPTASes for monotone dynamic programs, Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs, Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• Fast approximation algorithm for job sequencing with deadlines
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• An improved FPTAS for Restricted Shortest Path.
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Fast Approximation Algorithms for Knapsack Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Algorithms for Scheduling Independent Tasks
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Computing Partitions with Applications to the Knapsack Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• A simple efficient approximation scheme for the restricted shortest path problem