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
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
