Random sampling and approximation of MAX-CSPs

DOI10.1016/S0022-0000(03)00008-4zbMATH Open1160.68537MaRDI QIDQ1886453FDOQ1886453

Authors: Noga Alon, Marek Karpinski, W. Fernandez de la Vega, R. Kannan 

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)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Property testing and its connection to learning and approximation
• Title not available (Why is that?)
• Title not available (Why is that?)
• MAX-CUT has a randomized approximation scheme in dense graphs
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Quick approximation to matrices and applications
• On the best constants in the Khinchin inequality
• Random sampling and approximation of MAX-CSP problems
• Title not available (Why is that?)
• On the discrepancy of combinatorial rectangles
• Title not available (Why is that?)
• Property testers for dense constraint satisfaction programs on finite domains
• Title not available (Why is that?)

Cited In (20)

• Hypergraph regularity and random sampling
• Optimal cuts and partitions in tree metrics in polynomial time
• Sublinear-time Algorithms
• Co-clustering separately exchangeable network data
• The cut metric for probability distributions
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Testing odd-cycle-freeness in Boolean functions
• Grothendieck-type inequalities in combinatorial optimization
• Local and global expansion in random geometric graphs
• Moments of two-variable functions and the uniqueness of graph limits
• Numerical multilinear algebra and its applications
• Optimal graphon estimation in cut distance
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction
• Amplification and Derandomization without Slowdown
• Approximating sparse binary matrices in the cut-norm
• Bounds for graph regularity and removal lemmas
• A dichotomy for minimum cost graph homomorphisms
• Sublinear algorithms for MAXCUT and correlation clustering
• Testing Odd-Cycle-Freeness in Boolean Functions

This page was built for publication: Random sampling and approximation of MAX-CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1886453)