Pliability and approximating Max-CSPs
From MaRDI portal
Cites work
- \(L^{2}\)-spectral invariants and convergent sequences of finite graphs
- A birthday repetition theorem and complexity of approximating dense CSPs
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Separator Theorem for Planar Graphs
- Algorithms for graphs embeddable with few crossings per edge
- Applications of a Planar Separator Theorem
- Approximating dense MAX 2-CSPs
- Approximation Algorithms for Graph Homomorphism Problems
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs.
- Approximation schemes for covering and packing problems in image processing and VLSI
- Baker game and polynomial-time approximation schemes
- Bidimensionality: new connections between FPT algorithms and PTASs
- Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics
- Counting extensions
- Decomposing a graph into expanding subgraphs
- Diameter and treewidth in minor-closed graph families
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- Every property of hyperfinite graphs is testable
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Girth in graphs
- Grad and classes with bounded expansion. II: Algorithmic aspects
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 5485551 (Why is no real title available?)
- scientific article; zbMATH DE number 5776838 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 1256750 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- Improved approximation algorithms for label cover problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Introduction to Property Testing
- Large networks and graph limits
- Local Graph Partitions for Approximation and Testing
- Local tree-width, excluded minors, and approximation algorithms
- Lower bound of the Hadwiger number of graphs by their average degree
- MAX-CUT has a randomized approximation scheme in dense graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- New upper bounds on harmonious colorings
- Notes on graph product structure theory
- On fractional fragility rates of graph classes
- On the generalised colouring numbers of graphs that exclude a fixed minor
- On the Hardness of 4-Coloring a 3-Colorable Graph
- On the power of unique 2-prover 1-round games
- Optimization, approximation, and complexity classes
- P-Complete Approximation Problems
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- PCP characterizations of NP: toward a polynomially-small error-probability
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Proof verification and the hardness of approximation problems
- Property testers for dense constraint satisfaction programs on finite domains
- Property testing and its connection to learning and approximation
- PTAS for Sparse General-valued CSPs
- Random sampling and approximation of MAX-CSPs
- Random walks and forbidden minors II
- Reducibility among combinatorial problems
- Regular Partitions of Hypergraphs: Regularity Lemmas
- Strongly sublinear separators and polynomial expansion
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- Sublinear separators, fragility and subexponential expansion
- Szemerédi's lemma for the analyst
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- The complexity of finite-valued CSPs
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The intrinsic dimensionality of graphs
- Thin graph classes and polynomial-time approximation schemes
- Tree-depth, subgraph coloring and homomorphism bounds
- Treewidth of grid subsets
- Treewidth-pliability and PTAS for Max-CSPs
- Uniform local amenability
- Uniform local amenability implies property A
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- When is the evaluation of conjunctive queries tractable?
This page was built for publication: Pliability and approximating Max-CSPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7031998)
