Random sampling and approximation of MAX-CSPs
From MaRDI portal
Publication:1886453
DOI10.1016/S0022-0000(03)00008-4zbMath1160.68537MaRDI QIDQ1886453
Marek Karpinski, Noga Alon, Ravindran Kannan, Wenceslas Fernandez de la Vega
Publication date: 18 November 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items (18)
Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Testing Odd-Cycle-Freeness in Boolean Functions ⋮ Moments of two-variable functions and the uniqueness of graph limits ⋮ Bounds for graph regularity and removal lemmas ⋮ Optimal cuts and partitions in tree metrics in polynomial time ⋮ Hypergraph regularity and random sampling ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1. ⋮ Amplification and Derandomization without Slowdown ⋮ Co-clustering separately exchangeable network data ⋮ Sublinear Algorithms for MAXCUT and Correlation Clustering ⋮ Approximating sparse binary matrices in the cut-norm ⋮ Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing ⋮ Numerical multilinear algebra and its applications ⋮ Sublinear-time Algorithms ⋮ Optimal graphon estimation in cut distance ⋮ The Cut Metric for Probability Distributions ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Quick approximation to matrices and applications
- .879-approximation algorithms for MAX CUT and MAX 2SAT
- Property testers for dense constraint satisfaction programs on finite domains
- Property testing and its connection to learning and approximation
- Random sampling and approximation of MAX-CSP problems
- On the best constants in the Khinchin inequality
- On the discrepancy of combinatorial rectangles
- MAX-CUT has a randomized approximation scheme in dense graphs
- Probability Inequalities for Sums of Bounded Random Variables
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
This page was built for publication: Random sampling and approximation of MAX-CSPs
