When polynomial approximation meets exact computation
From MaRDI portal
Publication:5892165
DOI10.1007/s10288-015-0294-7zbMath1355.68128OpenAlexW811821385MaRDI QIDQ5892165
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
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