Randomized strategies for robust combinatorial optimization with approximate separation

DOI10.1007/S00453-023-01175-3MaRDI QIDQ6182680

Yasushi Kawase, Hanna Sumita

Publication date: 25 January 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

robust optimizationellipsoid methodmax-min fair allocationmaximum cardinality robustness problem

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
• A note on maximizing a submodular set function subject to a knapsack constraint
• Approximation algorithms for knapsack problems with cardinality constraints
• Randomized strategies for cardinality robustness in the knapsack problem
• Adaptive game playing using multiplicative weights
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing knapsack solutions with cardinality robustness
• Two linear approximation algorithms for the subset-sum problem
• Submodular functions and optimization.
• Robust Monotone Submodular Function Maximization
• Security and Game Theory
• Polynomial algorithms in linear programming
• Robust Matchings
• Robust Randomized Matchings
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Algorithmic Game Theory
• Robust Matchings and Matroid Intersections
• Robust Independence Systems
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

This page was built for publication: Randomized strategies for robust combinatorial optimization with approximate separation