Random sampling and approximation of MAX-CSPs

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)

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

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

• 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