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

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 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
Pages420-436
Number of pages17
ISBN (Print)9781611972108
DOIs
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

Other

Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
CountryJapan
CityKyoto
Period1/17/121/19/12

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

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

Cite this