Publication
SODA 2012
Conference paper

Concentration inequalities for nonlinear matroid intersection

View publication

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. Copyright © SIAM.

Date

Publication

SODA 2012

Authors

Share