A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs

DOI10.1007/s00453-018-00539-4zbMath1430.90535OpenAlexW2911133130MaRDI QIDQ2414864

Waleed Najy, Kazuhisa Makino, Khaled M. Elbassioni

Publication date: 17 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-00539-4

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

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

Uses Software

• CVX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On randomized fictitious play for approximating saddle points over convex sets
• Semi-infinite programming
• Faster and simpler approximation algorithms for mixed packing and covering problems
• Applications of second-order cone programming
• The weighted majority algorithm
• Second-order cone programming
• Introductory lectures on convex optimization. A basic course.
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• 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
• On combining machine learning with decision making
• An iterative method of solving a game
• Approximate Max-Min Resource Sharing for Structured Concave Optimization
• Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
• Graph Implementations for Nonsmooth Convex Programs
• Theory and Applications of Robust Optimization
• Oracle-Based Robust Optimization via Online Learning
• Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
• Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control
• Coordination Complexity of Parallel Price-Directive Decomposition
• A parallel approximation algorithm for positive linear programming
• Robust minimum variance beamforming
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Machine Learning: ECML 2004
• Algorithms – ESA 2004
• A Parallel Approximation Algorithm for Positive Semidefinite Programming
• Robust Portfolio Selection Problems
• Integer Programming and Combinatorial Optimization