Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation (Q4596147): Difference between revisions

Latest revision as of 20:03, 14 July 2024

scientific article; zbMATH DE number 6814262

Language	Label	Description	Also known as
English	Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation	scientific article; zbMATH DE number 6814262

Statements

instance of

scholarly article

0 references

title

Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation (English)

0 references

author

Vangelis Th. Paschos

0 references

published in

Optimization Theory, Decision Making, and Operations Research Applications

0 references

publication date

30 November 2017

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-1-4614-5134-1_1

0 references

cites work

Proof verification and the hardness of approximation problems

0 references

Q4258216

0 references

Q5668821

0 references

On approximation properties of the Independent set problem for degree 3 graphs

0 references

Fast algorithms for max independent set

0 references

Exact Algorithms for Dominating Clique Problems

0 references

Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms

0 references

Approximation of min coloring by moderately exponential algorithms

0 references

Efficient approximation of Min Set Cover by moderately exponential algorithms

0 references

Fast Algorithms for min independent dominating set

0 references

A Bottom-Up Method and Fast Algorithms for max independent set

0 references

Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms

0 references

Combining Two Worlds: Parameterised Approximation for Vertex Cover

0 references

Enumerating maximal independent sets with applications to graph colouring.

0 references

Fixed-Parameter Approximation: Conceptual Framework and Approximability Results

0 references

On Parameterized Approximability

0 references

Exact and approximate bandwidth

0 references

Exponential-time approximation of weighted set cover

0 references

Capacitated Domination Faster Than O(2 n )

0 references

On an approximation measure founded on the links between optimization and polynomial approximation theory

0 references

Parameterized Approximation Problems

0 references

Q4526990

0 references

Q2768314

0 references

A threshold of ln <i>n</i> for approximating set cover

0 references

Exact exponential algorithms.

0 references

Automata, Languages and Programming

0 references

An Exponential Time 2-Approximation Algorithm for Bandwidth

0 references

Approximating the minimum maximal independence number

0 references

Clique is hard to approximate within \(n^{1-\epsilon}\)

0 references

Which problems have strongly exponential complexity?

0 references

Approximation algorithms for combinatorial problems

0 references

Vertex packings: Structural properties and algorithms

0 references

Q5702337

0 references

Confronting hardness using a hybrid approach

0 references

Approximation algorithms for metric facility location and <i>k</i> -Median problems using the primal-dual schema and Lagrangian relaxation

0 references

Q4414647

0 references

Linear degree extractors and the inapproximability of max clique and chromatic number

0 references

Identifiers

zbMATH Open document ID

1375.68070

0 references

DOI

10.1007/978-1-4614-5134-1_1

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4596147

@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Q4258216
@@ Property / cites work: Q4258216 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5668821
@@ Property / cites work: Q5668821 / rank @@
+Normal rank
@@ Property / cites work @@
+On approximation properties of the Independent set problem for degree 3 graphs
+Normal rank
@@ Property / cites work @@
+Fast algorithms for max independent set
@@ Property / cites work: Fast algorithms for max independent set / rank @@
+Normal rank
@@ Property / cites work @@
+Exact Algorithms for Dominating Clique Problems
@@ Property / cites work: Exact Algorithms for Dominating Clique Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
+Normal rank
@@ Property / cites work @@
+Approximation of min coloring by moderately exponential algorithms
+Normal rank
@@ Property / cites work @@
+Efficient approximation of Min Set Cover by moderately exponential algorithms
+Normal rank
@@ Property / cites work @@
+Fast Algorithms for min independent dominating set
+Normal rank
@@ Property / cites work @@
+A Bottom-Up Method and Fast Algorithms for max independent set
+Normal rank
@@ Property / cites work @@
+Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
+Normal rank
@@ Property / cites work @@
+Combining Two Worlds: Parameterised Approximation for Vertex Cover
+Normal rank
@@ Property / cites work @@
+Enumerating maximal independent sets with applications to graph colouring.
+Normal rank
@@ Property / cites work @@
+Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
+Normal rank
@@ Property / cites work @@
+On Parameterized Approximability
@@ Property / cites work: On Parameterized Approximability / rank @@
+Normal rank
@@ Property / cites work @@
+Exact and approximate bandwidth
@@ Property / cites work: Exact and approximate bandwidth / rank @@
+Normal rank
@@ Property / cites work @@
+Exponential-time approximation of weighted set cover
+Normal rank
@@ Property / cites work @@
+Capacitated Domination Faster Than O(2 n )
@@ Property / cites work: Capacitated Domination Faster Than O(2 n ) / rank @@
+Normal rank
@@ Property / cites work @@
+On an approximation measure founded on the links between optimization and polynomial approximation theory
+Normal rank
@@ Property / cites work @@
+Parameterized Approximation Problems
@@ Property / cites work: Parameterized Approximation Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q4526990
@@ Property / cites work: Q4526990 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2768314
@@ Property / cites work: Q2768314 / rank @@
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+Exact exponential algorithms.
@@ Property / cites work: Exact exponential algorithms. / rank @@
+Normal rank
@@ Property / cites work @@
+Automata, Languages and Programming
@@ Property / cites work: Automata, Languages and Programming / rank @@
+Normal rank
@@ Property / cites work @@
+An Exponential Time 2-Approximation Algorithm for Bandwidth
+Normal rank
@@ Property / cites work @@
+Approximating the minimum maximal independence number
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for combinatorial problems
+Normal rank
@@ Property / cites work @@
+Vertex packings: Structural properties and algorithms
+Normal rank
@@ Property / cites work @@
+Q5702337
@@ Property / cites work: Q5702337 / rank @@
+Normal rank
@@ Property / cites work @@
+Confronting hardness using a hybrid approach
@@ Property / cites work: Confronting hardness using a hybrid approach / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for metric facility location and             <i>k</i>             -Median problems using the primal-dual schema and Lagrangian relaxation
+Normal rank
@@ Property / cites work @@
+Q4414647
@@ Property / cites work: Q4414647 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear degree extractors and the inapproximability of max clique and chromatic number
+Normal rank