Baby PIH: Parameterized inapproximability of min CSP
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 note on max k-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation
- A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
- Almost polynomial factor inapproximability for parameterized k-clique
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests
- Approximating k-median via pseudo-approximation
- Approximation algorithms for NP-hard problems.
- 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
- Combinatorial gap theorem and reductions between promise CSPs
- 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
- Fixed-parameter approximation schemes for weighted flowtime
- From gap-ETH to FPT-inapproximability: clique, dominating set, and more
- Graph-Theoretic Concepts in Computer Science
- High dimensional expanders imply agreement expanders
- scientific article; zbMATH DE number 7561535 (Why is no real title available?)
- Lossy kernelization
- On colouring random graphs
- 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 hardness of approximating label-cover
- On the hardness of approximating minimization problems
- On the Parameterized Complexity of Approximating Dominating Set
- Parallel repetition in projection games and a concentration bound
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- Partitioning a graph into small pieces with applications to path transversal
- 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
- Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
Cited in
(4)- Parameterized inapproximability hypothesis under ETH
- Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
- On average baby PIH and its applications
- Parameterized approximability for modular linear equations
This page was built for publication: Baby PIH: Parameterized inapproximability of min CSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866466)
