Dependent randomized rounding via exchange properties of combinatorial structures

DOI10.1109/FOCS.2010.60MaRDI QIDQ6990291zbMATH OpenFDO

Authors Jan Vondrák, Chandra Chekuri, Rico Zenklusen

Publication date 29 April 2025

Full work available at URL https://doi.org/10.1109/FOCS.2010.60

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cited in

(11)

• The outer limits of contention resolution on matroids and connections to the secretary problem
• Optimal streaming algorithms for submodular maximization with cardinality constraints
• Concentration of submodular functions and read-k families under negative dependence
• Approximation algorithms for _p-shortest path and _p-group Steiner tree
• Polylogarithmic approximations for robust s-t path
• Subquadratic submodular maximization with a general matroid constraint
• Lower bounds for matroid optimization problems with a linear constraint
• Separating coverage and submodular: maximization subject to a cardinality constraint
• From contention resolution to matroid secretary and back
• Robust min-max (regret) optimization using ordered weighted averaging
• Covering a few submodular constraints and applications

This page was built for publication: Dependent randomized rounding via exchange properties of combinatorial structures

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