Concentration inequalities for nonlinear matroid intersection

Konstantin Makarychev, Warren Schudy, Maxim Sviridenko

Abstract

In this work we propose new randomized rounding algorithms for matroid intersection and matroid base polytopes. We prove concentration inequalities for polynomial objective functions and constraints ...
BibTeX
@inproceedings{makarychev2015concentration,
  author = {Konstantin Makarychev and Warren Schudy and Maxim Sviridenko},
  title = {{Concentration inequalities for nonlinear matroid intersection}},
  booktitle = {Random Struct. Algorithms},
  year = {2015},
  url = {https://openreview.net/forum?id=sPR2xM5dfSJ},
}

Loading related content...

Figure