Concentration inequalities for nonlinear matroid intersection

Konstantin Makarychev*, Warren Schudy, Maxim Sviridenko

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 that have numerous applications and can be used in approximation algorithms for Minimum Quadratic Spanning Tree, Unrelated Parallel Machines Scheduling and Scheduling with Time Windows and Nonlinear objectives. We also show applications related to Constraint Satisfaction and Dense Polynomial optimization.

Original languageEnglish (US)
Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
PublisherAssociation for Computing Machinery
Number of pages17
ISBN (Print)9781611972108
StatePublished - 2012
Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
Duration: Jan 17 2012Jan 19 2012

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Concentration inequalities for nonlinear matroid intersection'. Together they form a unique fingerprint.

Cite this