Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms

Petros Drineas, Ravi Kannan, Michael W. Mahoney

Abstract

Recent work in the analysis of randomized approximation algorithms for NP-hard optimization problems has involved approximating the solution to a problem by the solution of a related sub-problem of...
BibTeX
@inproceedings{drineas2005sampling,
  author = {Petros Drineas and Ravi Kannan and Michael W. Mahoney},
  title = {{Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms}},
  booktitle = {STACS},
  year = {2005},
  doi = {10.1007/978-3-540-31856-9\_5},
}

Loading related content...

Figure