Improved bounds in stochastic matching and optimization

DOI10.1007/s00453-017-0383-4zbMath1423.90158OpenAlexW2767081117MaRDI QIDQ1755741

Pan Xu, Alok Baveja, Amit Chavan, Aravind Srinivasan, Andrei Nikiforov

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5299/

zbMATH Keywords

linear programmingstochastic optimizationapproximation algorithmsrandomized algorithms

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the fractional matching polytope of a hypergraph
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Correlation inequalities on some partially ordered sets
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Linear Programming under Uncertainty
• The Design of Approximation Algorithms
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Improved Approximation Algorithms for Stochastic Matching
• An approximation scheme for stochastic linear programming and its application to stochastic integer programs
• Dependent rounding and its applications to approximation algorithms
• When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
• Approximating Matches Made in Heaven
• Introduction to Stochastic Programming
• A constant-factor approximation for stochastic Steiner forest
• Finding Large Independent Sets in Graphs and Hypergraphs
• Approximation Algorithms for Stochastic Inventory Control Models
• LP Rounding Approximation Algorithms for Stochastic Network Design

This page was built for publication: Improved bounds in stochastic matching and optimization