Premium
Concentration inequalities for nonlinear matroid intersection
Author(s) -
Makarychev Konstantin,
Schudy Warren,
Sviridenko Maxim
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20514
Subject(s) - matroid , weighted matroid , oriented matroid , rounding , matroid partitioning , mathematics , intersection (aeronautics) , combinatorics , randomized rounding , time complexity , scheduling (production processes) , polytope , spanning tree , nonlinear system , discrete mathematics , mathematical optimization , approximation algorithm , computer science , graphic matroid , engineering , aerospace engineering , operating system , physics , quantum mechanics
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. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 541–571, 2015