A birthday repetition theorem and complexity of approximating dense CSPs
From MaRDI portal
(Redirected from Publication:5111409)
Recommendations
Cited in
(48)- $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
- Lossy kernelization of same-size clustering
- FPT approximation using treewidth: capacitated vertex cover, target set selection and vector dominating set
- New support size bounds for integer programming, applied to makespan minimization on uniformly related machines
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Imperfect gaps in Gap-ETH and PCPs
- Lower bounds for approximate (\& exact) k-disjoint-shortest-paths
- Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- On parameterized approximation algorithms for balanced clustering
- Parameterized approximation algorithms for bidirected Steiner network problems
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- To close is easier than to open: dual parameterization to \(k\)-median
- Changing induced subgraph isomorphisms under extended reconfiguration rules
- Complexity of minimum-size arc-inconsistency explanations
- A PTAS framework for clustering problems in doubling metrics
- Approximation and hardness of shift-bribery
- Local proofs approaching the witness length
- Pliability and approximating Max-CSPs
- Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation
- Tight hardness results for training depth-2 ReLU networks
- Lower bounds for approximate (\& exact) \(k\)-\textsc{Disjoint-Shortest-Paths}
- Tight approximation and kernelization bounds for vertex-disjoint shortest paths
- Improved parameterized approximation for balanced \(k\)-median
- Better guarantees for individual fairness k-median
- A note on the concrete hardness of the shortest independent vector in lattices
- 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 \(\ell_{p}\) norms
- scientific article; zbMATH DE number 7561535 (Why is no real title available?)
- scientific article; zbMATH DE number 7650083 (Why is no real title available?)
- Approximation schemes for k-facility location
- Refinements of the k-tree Algorithm for the Generalized Birthday Problem
- Tree decompositions meet induced matchings: beyond max weight independent set
- Short Proofs Are Hard to Find
- A gap-ETH-tight approximation scheme for Euclidean TSP
- Computing tree decompositions with small independence number
- On Geometric Set Cover for Orthants
- New tools and connections for exponential-time approximation
- Changing induced subgraph isomorphisms under extended reconfiguration rules
- Applications of random algebraic constructions to hardness of approximation
- Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
- A tight lower bound for planar Steiner orientation
- Lower tails via relative entropy
- Hardness of approximating bounded-degree max 2-CSP and independent set on k-claw-free graphs
- Improved approximation algorithm for individual fairness k-median
- Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back
- Integrality gaps for colorful matchings
- Lossy kernelization of same-size clustering
This page was built for publication: A birthday repetition theorem and complexity of approximating dense CSPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111409)
