Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
DOI10.1007/978-1-4614-5134-1_1zbMATH Open1375.68070OpenAlexW94740613MaRDI QIDQ4596147FDOQ4596147
Authors: Vangelis Th. Paschos 
Publication date: 30 November 2017
Published in: Optimization Theory, Decision Making, and Operations Research Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-1-4614-5134-1_1
Recommendations
- Moderately exponential approximation
- Moderately exponential time and fixed parameter approximation algorithms
- When polynomial approximation meets exact computation
- When polynomial approximation meets exact computation
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- A threshold of ln n for approximating set cover
- Approximation algorithms for combinatorial problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Title not available (Why is that?)
- Exact exponential algorithms.
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Which problems have strongly exponential complexity?
- Proof verification and the hardness of approximation problems
- Parameterized Approximation Problems
- Automata, Languages and Programming
- Approximating the minimum maximal independence number
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Confronting hardness using a hybrid approach
- Vertex packings: Structural properties and algorithms
- Title not available (Why is that?)
- Fast algorithms for max independent set
- Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
- Enumerating maximal independent sets with applications to graph colouring.
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- Title not available (Why is that?)
- Exact and approximate bandwidth
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- On Parameterized Approximability
- An exponential time 2-approximation algorithm for bandwidth
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Title not available (Why is that?)
- On approximation properties of the Independent set problem for degree 3 graphs
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- A bottom-up method and fast algorithms for Max Independent Set
- Exact algorithms for dominating clique problems (extended abstract)
- Title not available (Why is that?)
- Fast algorithms for \textsc{min independent dominating set}
- Capacitated domination faster than \(O(2^{n })\)
Cited In (1)
This page was built for publication: Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4596147)
