Moderately exponential time and fixed parameter approximation algorithms (Q2868915): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1080/02331934.2012.704515
+Normal rank
@@ Property / OpenAlex ID @@
+W2019648557
@@ Property / OpenAlex ID: W2019648557 / rank @@
+Normal rank
@@ 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 @@
+The Steiner problem with edge lengths 1 and 2
@@ Property / cites work: The Steiner problem with edge lengths 1 and 2 / rank @@
+Normal rank
@@ Property / cites work @@
+Set Partitioning via Inclusion-Exclusion
@@ Property / cites work: Set Partitioning via Inclusion-Exclusion / rank @@
+Normal rank
@@ Property / cites work @@
+Computing small partial coverings
@@ Property / cites work: Computing small partial coverings / rank @@
+Normal rank
@@ Property / cites work @@
+The parameterized approximability of TSP with deadlines
+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 max independent set
@@ Property / cites work: Fast algorithms for max independent set / rank @@
+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 @@
+Vertex Cover: Further Observations and Further Improvements
+Normal rank
@@ Property / cites work @@
+Improved exact algorithms for MAX-SAT
@@ Property / cites work: Improved exact algorithms for MAX-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Exponential-time approximation of weighted set cover
+Normal rank
@@ Property / cites work @@
+Exact and approximate bandwidth
@@ Property / cites work: Exact and approximate bandwidth / rank @@
+Normal rank
@@ Property / cites work @@
+MAX SAT approximation beyond the limits of polynomial-time approximation
+Normal rank
@@ Property / cites work @@
+The PCP theorem by gap amplification
@@ Property / cites work: The PCP theorem by gap amplification / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized Approximation Problems
@@ Property / cites work: Parameterized Approximation Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating MAX SAT by moderately exponential and parameterized algorithms
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+Approximating the bandwidth via volume respecting embeddings
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Exact exponential algorithms.
@@ Property / cites work: Exact exponential algorithms. / 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 @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Worst-case study of local search for MAX-\(k\)-SAT.
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for maximum graph partitioning problems
+Normal rank
@@ Property / cites work @@
+Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
+Normal rank
@@ Property / cites work @@
+Improved Upper Bounds for Partial Vertex Cover
@@ Property / cites work: Improved Upper Bounds for Partial Vertex Cover / rank @@
+Normal rank
@@ Property / cites work @@
+Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
+Normal rank
@@ Property / cites work @@
+Vertex packings: Structural properties and algorithms
+Normal rank
@@ Property / cites work @@
+Optimization, approximation, and complexity classes
+Normal rank
@@ Property / cites work @@
+Q4782696
@@ Property / cites work: Q4782696 / rank @@
+Normal rank