Concentration inequalities for nonlinear matroid intersection

Konstantin Makarychev, Warren Schudy, Maxim Sviridenko*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 has 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)
Pages (from-to)541-571
Number of pages31
JournalRandom Structures and Algorithms
Volume46
Issue number3
DOIs
StatePublished - May 1 2015

Keywords

  • Approximation algorithms
  • Measure concentration
  • Randomized rounding

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

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

Cite this