When polynomial approximation meets exact computation
From MaRDI portal
Publication:5915964
DOI10.1007/s10479-018-2986-9zbMath1434.68202OpenAlexW2885672520WikidataQ129443444 ScholiaQ129443444MaRDI QIDQ5915964
Publication date: 6 March 2019
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-018-2986-9
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- 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
- When polynomial approximation meets exact computation
- 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
