Concentration inequalities for nonlinear matroid intersection

Konstantin Makarychev; Warren Schudy; Maxim Sviridenko

doi:10.1137/1.9781611973099.36

Concentration inequalities for nonlinear matroid intersection

Konstantin Makarychev^*, Warren Schudy, Maxim Sviridenko

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
Publisher	Association for Computing Machinery
Pages	420-436
Number of pages	17
ISBN (Print)	9781611972108
DOIs	https://doi.org/10.1137/1.9781611973099.36
State	Published - 2012
Event	23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan Duration: Jan 17 2012 → Jan 19 2012

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other	23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
Country/Territory	Japan
City	Kyoto
Period	1/17/12 → 1/19/12

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1137/1.9781611973099.36

Cite this

@inproceedings{2d44b61e6b124ff08c6b50f0ecb02e1d,

title = "Concentration inequalities for nonlinear matroid intersection",

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.",

author = "Konstantin Makarychev and Warren Schudy and Maxim Sviridenko",

year = "2012",

doi = "10.1137/1.9781611973099.36",

language = "English (US)",

isbn = "9781611972108",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "420--436",

booktitle = "Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012",

}

Makarychev, K, Schudy, W & Sviridenko, M 2012, Concentration inequalities for nonlinear matroid intersection. in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 420-436, 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 1/17/12. https://doi.org/10.1137/1.9781611973099.36

Concentration inequalities for nonlinear matroid intersection. / Makarychev, Konstantin; Schudy, Warren; Sviridenko, Maxim.
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Association for Computing Machinery, 2012. p. 420-436 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Concentration inequalities for nonlinear matroid intersection

AU - Makarychev, Konstantin

AU - Schudy, Warren

AU - Sviridenko, Maxim

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84860158300&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860158300&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.36

DO - 10.1137/1.9781611973099.36

M3 - Conference contribution

AN - SCOPUS:84860158300

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 420

EP - 436

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -

Concentration inequalities for nonlinear matroid intersection

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this