Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms

DOI10.1002/rsa.20196zbMath1192.90115OpenAlexW3083201583MaRDI QIDQ3503606

Michael W. Mahoney, Petros Drineas, Ravindran 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)

Related Items (1)

Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of unique 2-prover 1-round games
• Sampling lower bounds via information theory
• Matrix Analysis
• Smoothed analysis of algorithms
• STACS 2005
• Monte Carlo strategies in scientific computing

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