Improved approximation algorithms for the Min-Max selecting items problem

DOI10.1016/j.ipl.2013.07.011zbMath1284.68662arXiv1304.7403OpenAlexW2057251645MaRDI QIDQ2445242

Benjamin Doerr

Publication date: 14 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.7403

zbMATH Keywords

approximation algorithmrobust optimizationderandomizationrandomized rounding

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (7)

Robust recoverable and two-stage selection problems ⋮ On recoverable and two-stage robust selection problems with budgeted uncertainty ⋮ Approximating combinatorial optimization problems with the ordered weighted averaging criterion ⋮ Combinatorial optimization problems with uncertain costs and the OWA criterion ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ Approximability of the robust representatives selection problem ⋮ Robust Single Machine Scheduling Problem with Weighted Number of Late Jobs Criterion

Cites Work

• Unnamed Item
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Robust discrete optimization and its applications
• Approximating the min-max (regret) selecting items problem
• A randomized algorithm for the min-Max selecting items problem with uncertain weights
• Randomized Rounding in the Presence of a Cardinality Constraint
• Generating Randomized Roundings with Cardinality Constraints and Derandomizations
• STACS 2005

This page was built for publication: Improved approximation algorithms for the Min-Max selecting items problem