Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations

DOI10.1007/s00453-022-00987-zOpenAlexW4293079062WikidataQ114229327 ScholiaQ114229327MaRDI QIDQ5970783

Khaled M. Elbassioni

Publication date: 8 December 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-00987-z

zbMATH Keywords

linear programmingrobust optimizationdiscrete optimizationapproximation algorithmsrandomized rounding

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards more practical linear programming-based techniques for algorithmic mechanism design
• Approximate formulations for 0-1 knapsack sets
• Geometric algorithms and combinatorial optimization.
• Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
• Robust discrete optimization and network flows
• The quadratic shortest path problem: complexity, approximability, and solution methods
• Robust optimization-methodology and applications
• Robust combinatorial optimization with variable budgeted uncertainty
• Robust scheduling with budgeted uncertainty
• A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs
• Approximation of the quadratic set covering problem
• A note on the Bertsimas \& Sim algorithm for robust combinatorial optimization problems
• Tractable approximations to robust conic optimization problems
• Approximation algorithms for covering/packing integer programs
• Robust Convex Optimization
• A Dynamic Programming Approach for a Class of Robust Optimization Problems
• Optimization over Integers with Robustness in Cost and Few Constraints
• Fast Convex Decomposition for Truthful Social Welfare Approximation
• Introduction to Stochastic Programming
• Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems
• Theory and Applications of Robust Optimization
• Robust Solutions to Uncertain Semidefinite Programs
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Randomized metarounding
• Oblivious Rounding and the Integrality Gap
• Robust constrained shortest path problems under budgeted uncertainty
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Algorithms to Approximate Column-sparse Packing Problems
• Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games
• Analytical approach to parallel repetition
• Robust Combinatorial Optimization with Exponential Scenarios

This page was built for publication: Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations