Concentration inequalities for nonlinear matroid intersection
Lists
Only you see this
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.
BibTeX
@inproceedings{makarychev2015concentration,
author = {Konstantin Makarychev and Warren Schudy and Maxim Sviridenko},
title = {{Concentration inequalities for nonlinear matroid intersection}},
booktitle = {Random Struct. Algorithms},
year = {2015},
url = {https://openreview.net/forum?id=sPR2xM5dfSJ},
}Loading related content...