Parameterized inapproximability hypothesis under ETH
From MaRDI portal
Cites work
- A constant-factor approximation algorithm for the k-median problem
- A local search approximation algorithm for \(k\)-means clustering
- A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
- A note on max k-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation
- A parameterized approximation scheme for min k-cut
- A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
- A simplified NP-complete satisfiability problem
- A threshold of ln n for approximating set cover
- An FPT algorithm beating 2-approximation for \(k\)-cut
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Analytical approach to parallel repetition
- Applications of random algebraic constructions to hardness of approximation
- Approximating k-median via pseudo-approximation
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Baby PIH: Parameterized inapproximability of min CSP
- Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
- Chamberlin-Courant rule with approval ballots: approximating the MaxCover problem with bounded frequencies in FPT time
- Computational Complexity
- Constant approximating k-clique is w[1]-hard
- Constant approximating Parameterized \(k\)-\textsc{SetCover} is W[2]-hard
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- Exponentially-hard gap-CSP and local PRG via local hardcore functions
- Faster exact and approximate algorithms for k-cut
- Fixed-Parameter and Approximation Algorithms: A New Look
- Fixed-parameter approximation schemes for weighted flowtime
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Graph-Theoretic Concepts in Computer Science
- Greedy Strikes Back: Improved Facility Location Algorithms
- scientific article; zbMATH DE number 5485539 (Why is no real title available?)
- scientific article; zbMATH DE number 7561535 (Why is no real title available?)
- Improved hardness of approximating k-clique under ETH
- Interactive proofs and the hardness of approximating cliques
- Introduction to Property Testing
- List decoding tensor products and interleaved codes
- On hardness of approximation of parameterized set cover and label cover: threshold graphs from error correcting codes
- On lower bounds of approximating parameterized k-clique
- On the complexity of k-SAT
- On the efficiency of local decoding procedures for error-correcting codes
- On the Parameterized Complexity of Approximating Dominating Set
- On the parameterized intractability of determinant maximization
- Parallel repetition in projection games and a concentration bound
- Parameterized approximation schemes for clustering with general norm objectives
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- Parameterized inapproximability for Steiner orientation by gap amplification
- Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
- Parameterized Intractability of Even Set and Shortest Vector Problem
- Parametrized complexity theory.
- Partitioning a graph into small pieces with applications to path transversal
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Revisiting alphabet reduction in Dinur’s PCP.
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Self-testing/correcting with applications to numerical problems
- The complexity of satisfiability of small depth circuits
- The constant inapproximability of the parameterized dominating set problem
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- The parameterized complexity of the k-biclique problem
- The PCP theorem by gap amplification
- Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
- Which problems have strongly exponential complexity?
This page was built for publication: Parameterized inapproximability hypothesis under ETH
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6892972)
