A Multiplicative Weights Update Algorithm for Packing and Covering Semi-infinite Linear Programs

DOI10.1007/978-3-319-51741-4_7zbMath1430.90534OpenAlexW2569277880MaRDI QIDQ2971158

Kazuhisa Makino, Waleed Najy, Khaled M. Elbassioni

Publication date: 4 April 2017

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-51741-4_7

zbMATH Keywords

robust optimizationsecond-order cone programmingpacking and coveringmultiplicative weights update

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27) Semi-infinite programming (90C34)

Related Items

Recent contributions to linear semi-infinite optimization: an update

Uses Software

• CVX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On randomized fictitious play for approximating saddle points over convex sets
• Semi-infinite programming
• The weighted majority algorithm
• Second-order cone programming
• Adaptive game playing using multiplicative weights
• Robust optimization-methodology and applications
• Almost optimal set covers in finite VC-dimension
• A sublinear-time randomized approximation algorithm for matrix games
• An iterative method of solving a game
• Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
• Graph Implementations for Nonsmooth Convex Programs
• Oracle-Based Robust Optimization via Online Learning
• Algorithms – ESA 2004
• A Parallel Approximation Algorithm for Positive Semidefinite Programming
• Robust Portfolio Selection Problems
• Integer Programming and Combinatorial Optimization