Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation

DOI10.1007/978-1-4614-5134-1_1MaRDI QIDQ4596147zbMATHOpenAlexFDO

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

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

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

Cites work

scientific article; zbMATH DE number 1330033 (Why is no real title available?)
scientific article; zbMATH DE number 1953201 (Why is no real title available?)
scientific article; zbMATH DE number 1559541 (Why is no real title available?)
scientific article; zbMATH DE number 3400923 (Why is no real title available?)
scientific article; zbMATH DE number 2221549 (Why is no real title available?)
A bottom-up method and fast algorithms for Max Independent Set
A threshold of ln n for approximating set cover
An exponential time 2-approximation algorithm for bandwidth
Approximating the minimum maximal independence number
Approximation algorithms for combinatorial problems
Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
Approximation of min coloring by moderately exponential algorithms
Automata, Languages and Programming
Capacitated domination faster than \(O(2^{n })\)
Clique is hard to approximate within \(n^{1-\epsilon}\)
Combining Two Worlds: Parameterised Approximation for Vertex Cover
Confronting hardness using a hybrid approach
Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
Efficient approximation of Min Set Cover by moderately exponential algorithms
Enumerating maximal independent sets with applications to graph colouring.
Exact algorithms for dominating clique problems (extended abstract)
Exact and approximate bandwidth
Exact exponential algorithms.
Exponential-time approximation of weighted set cover
Fast algorithms for \textsc{min independent dominating set}
Fast algorithms for max independent set
Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
Linear degree extractors and the inapproximability of max clique and chromatic number
On Parameterized Approximability
On an approximation measure founded on the links between optimization and polynomial approximation theory
On approximation properties of the Independent set problem for degree 3 graphs
Parameterized Approximation Problems
Proof verification and the hardness of approximation problems
Vertex packings: Structural properties and algorithms
Which problems have strongly exponential complexity?

Cited in

(6)

Moderately exponential approximation
Moderately exponential time and fixed parameter approximation algorithms
When polynomial approximation meets exact computation
Exponential approximation schemata for some network design problems
Super-polynomial approximation branching algorithms
Preface

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)