Concentration inequalities for nonlinear matroid intersection1. Issue 3 (27th July 2013)

• Record Type: Journal Article
• Authors: Makarychev, Konstantin; Schudy, Warren; Sviridenko, Maxim
• Is Part Of: Random structures & algorithms. Volume 46:Issue 3(2015)
• Page Start: 541
• Page End: 571
• Publication Date: 2013-07-27
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20514
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>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</p> </abstract>