When polynomial approximation meets exact computation

DOI10.1007/s10288-015-0294-7zbMath1355.68128OpenAlexW811821385MaRDI QIDQ5892165

Vangelis Th. Paschos

Publication date: 17 September 2015

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10288-015-0294-7

zbMATH Keywords

complexitypolynomial approximationexact algorithmmoderately exponential approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (5)

Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ When polynomial approximation meets exact computation ⋮ 4OR comes of age. Editorial note ⋮ Preface ⋮ Moderate exponential-time algorithms for scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential approximation schemata for some network design problems
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Exact exponential algorithms.
• Approximating the minimum maximal independence number
• Enumerating maximal independent sets with applications to graph colouring.
• Exact and approximate bandwidth
• Exact algorithms for exact satisfiability and number of perfect matchings
• Exponential-time approximation of weighted set cover
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• Fast algorithms for min independent dominating set
• On subexponential and FPT-time inapproximability
• Exact Algorithms for Maximum Independent Set
• Proof verification and the hardness of approximation problems
• The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
• A Dynamic Programming Approach to Sequencing Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Set Partitioning via Inclusion-Exclusion
• Capacitated Domination Faster Than O(2 n )
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• Expected Computation Time for Hamiltonian Path problem
• Vertex packings: Structural properties and algorithms
• On approximation properties of the Independent set problem for degree 3 graphs
• Automata, Languages and Programming
• Approximation and Online Algorithms
• The PCP theorem by gap amplification
• MAX SAT approximation beyond the limits of polynomial-time approximation

This page was built for publication: When polynomial approximation meets exact computation