Concentration inequalities for nonlinear matroid intersection

DOI10.1002/RSA.20514MaRDI QIDQ5252262zbMATH OpenOpenAlexFDO

Authors Konstantin Makarychev, Warren Schudy, Maxim Sviridenko

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 algorithmsmeasure concentrationrandomized rounding

Mathematics Subject Classification ID

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

Recommendations

• Concentration inequalities for nonlinear matroid intersection
• Multi-budgeted matchings and matroid intersection via dependent rounding
• Approximate multi-matroid intersection via iterative refinement
• Approximate multi-matroid intersection via iterative refinement
• Online matroid intersection: beating half for random arrival

Cites work

• A multiobjective branch-and-bound framework: application to the biobjective spanning tree problem
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• A unified approach to scheduling on unrelated parallel machines
• An approximation algorithm for the generalized assignment problem
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• Approximate nonlinear optimization over weighted independence systems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Concentration Inequalities and Martingale Inequalities: A Survey
• Concentration inequalities. A nonasymptotic theory of independence
• Concentration of Measure for the Analysis of Randomized Algorithms
• Concentration of multivariate polynomials and its applications
• Concentration of non‐Lipschitz functions and applications
• Convex programming for scheduling unrelated parallel machines
• Convex quadratic and semidefinite programming relaxations in scheduling
• Fuzzy quadratic minimum spanning tree problem
• scientific article; zbMATH DE number 35513 (Why is no real title available?)
• scientific article; zbMATH DE number 1305540 (Why is no real title available?)
• scientific article; zbMATH DE number 2013754 (Why is no real title available?)
• scientific article; zbMATH DE number 2109192 (Why is no real title available?)
• Minimum spanning trees made easier via multi-objective optimization
• Moment inequalities for functions of independent random variables
• Multi-budgeted matchings and matroid intersection via dependent rounding
• Nonlinear bipartite matching
• Nonlinear Matroid Optimization and Experimental Design
• On the concentration of multivariate polynomials with small expectation
• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Submodular maximization over multiple matroids via generalized exchange properties
• Survey Paper—Time Window Constrained Routing and Scheduling Problems
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm

Cited in

(3)

• Multi-budgeted matchings and matroid intersection via dependent rounding
• Pipage rounding, pessimistic estimators and matrix concentration
• Concentration inequalities for nonlinear matroid intersection

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5252262)