Concentration inequalities for nonlinear matroid intersection

Konstantin Makarychev; Warren Schudy; Maxim Sviridenko

doi:10.1002/rsa.20514

Concentration inequalities for nonlinear matroid intersection

Konstantin Makarychev, Warren Schudy, Maxim Sviridenko^*

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	541-571
Number of pages	31
Journal	Random Structures and Algorithms
Volume	46
Issue number	3
DOIs	https://doi.org/10.1002/rsa.20514
State	Published - May 1 2015

Keywords

Approximation algorithms
Measure concentration
Randomized rounding

ASJC Scopus subject areas

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1002/rsa.20514

Cite this

@article{25c7ebfeb2544d37859719786a4c92df,

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

keywords = "Approximation algorithms, Measure concentration, Randomized rounding",

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

note = "Publisher Copyright: {\textcopyright} 2013 Wiley Periodicals, Inc.",

year = "2015",

month = may,

day = "1",

doi = "10.1002/rsa.20514",

language = "English (US)",

volume = "46",

pages = "541--571",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "3",

}

TY - JOUR

T1 - Concentration inequalities for nonlinear matroid intersection

AU - Makarychev, Konstantin

AU - Schudy, Warren

AU - Sviridenko, Maxim

PY - 2015/5/1

Y1 - 2015/5/1

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

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

KW - Approximation algorithms

KW - Measure concentration

KW - Randomized rounding

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

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

U2 - 10.1002/rsa.20514

DO - 10.1002/rsa.20514

M3 - Article

AN - SCOPUS:84924760371

SN - 1042-9832

VL - 46

SP - 541

EP - 571

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 3

ER -

Concentration inequalities for nonlinear matroid intersection

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this