Improved randomized approximation algorithms for lot-sizing problems

DOI10.1007/3-540-61310-2_27zbMath1415.90109OpenAlexW1596341019MaRDI QIDQ4645935

Chung-Piaw Teo, Dimitris J. Bertsimas

Publication date: 11 January 2019

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61310-2_27

zbMATH Keywords

approximation algorithmoptimal stationary policyjoint replenishment problembase periodimprove approximation algorithm

Mathematics Subject Classification ID

Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Establishing Consistent and Realistic Reorder Intervals in Production-Distribution Systems
• 98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer Systems
• Note—A Dynamic Programming Algorithm for Joint Replenishment Under General Order Cost Functions
• The Economic Lot-Scheduling Problem: Achieving Feasibility Using Time-Varying Lot Sizes
• Minimizing Separable Convex Objectives on Arbitrarily Directed Trees of Variable Upper Bound Constraints
• Lot Sizing Policies for Finite Production Rate Assembly Systems
• Simple Power-of-Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with General Joint Setup Costs
• Optimal Power-of-Two Replenishment Strategies in Capacitated General Production/Distribution Networks
• A 98%-Effective Lot-Sizing Rule for a Multi-Product, Multi-Stage Production / Inventory System
• Rounding Off to Powers of Two in Continuous Relaxations of Capacitated Lot Sizing Problems
• Approximation Procedures for the One-Warehouse Multi-Retailer System
• Nonlinear formulations and improved randomized approximation algorithms for multicut problems
• Convex separable optimization is not much harder than linear optimization