Concentration inequalities for nonlinear matroid intersection

DOI10.1002/rsa.20514zbMath1312.05032OpenAlexW1877735794MaRDI QIDQ5252262

Warren Schudy, M. I. Sviridenko, Konstantin Makarychev

Publication date: 29 May 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20514

zbMATH Keywords

approximation algorithmsrandomized roundingmeasure concentration

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fuzzy quadratic minimum spanning tree problem
• Minimum spanning trees made easier via multi-objective optimization
• Nonlinear bipartite matching
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• An approximation algorithm for the generalized assignment problem
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• Moment inequalities for functions of independent random variables
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• Concentration Inequalities
• A Multiobjective Branch-and-Bound Framework: Application to the Biobjective Spanning Tree Problem
• Approximate Nonlinear Optimization over Weighted Independence Systems
• Convex quadratic and semidefinite programming relaxations in scheduling
• Nonlinear Matroid Optimization and Experimental Design
• Concentration Inequalities and Martingale Inequalities: A Survey
• A unified approach to scheduling on unrelated parallel machines
• Convex programming for scheduling unrelated parallel machines
• Survey Paper—Time Window Constrained Routing and Scheduling Problems
• On the concentration of multivariate polynomials with small expectation
• Concentration of non‐Lipschitz functions and applications
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Concentration of Measure for the Analysis of Randomized Algorithms
• Concentration of multivariate polynomials and its applications

This page was built for publication: Concentration inequalities for nonlinear matroid intersection