Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms

DOI10.1002/RSA.20196MaRDI QIDQ3503606zbMATH OpenOpenAlexFDO

Authors Michael W. Mahoney, Petros Drineas, R. Kannan

Publication date 5 June 2008

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20196

zbMATH Keywords

CUR matrix decompositionMax-Cut algorithmSampling Linear Programs

Mathematics Subject Classification ID

Linear programming (90C05)

Recommendations

• STACS 2005
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Efficient and near-optimal algorithms for sampling connected subgraphs
• Sampling and cost-sharing: approximation algorithms for stochastic optimization problems
• The power of subsampling in submodular maximization
• A randomized approximation scheme for metric MAX-CUT
• The hardness of sampling connected subgraphs
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
• Approximate Max k-Cut with subgraph guarantee
• On the approximability of Max-Cut

Cites work

• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• scientific article; zbMATH DE number 1305418 (Why is no real title available?)
• scientific article; zbMATH DE number 2079343 (Why is no real title available?)
• Matrix Analysis
• Monte Carlo strategies in scientific computing
• On the power of unique 2-prover 1-round games
• STACS 2005
• Sampling lower bounds via information theory
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

Cited in

(4)

• STACS 2005
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• Random sampling in cut, flow, and network design problems

This page was built for publication: Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms

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