Invited Session Tue.3.H 0111

Tuesday, 15:15 - 16:45 h, Room: H 0111

Cluster 13: Logistics, traffic, and transportation [...]

Approximation algorithms for supply chain management and logistics optimization models


Chair: Retsef Levi



Tuesday, 15:15 - 15:40 h, Room: H 0111, Talk 1

Tim Carnes
A primal-dual approximation algorithm for air ambulance routing and deployment

Coauthor: David B. Shmoys


We present a primal-dual 2-approximation algorithm for the k-location routing problem, that models choosing k locations for vehicles and routing each vehicle in a tour to serve a set of requests, where the cost is the total tour length. This is the first constant approximation algorithm for this problem and has real-world applications; this is part of a broader effort for Ornge, which transports medical patients. Our work builds and improves upon work of Goemans & Williamson and Jain & Vazirani.



Tuesday, 15:45 - 16:10 h, Room: H 0111, Talk 2

Gonzalo Romero
Allocating subsidies to minimize a commodity's market price - a network design approach

Coauthors: Retsef Levi, Georgia Perakis


We study the problem faced by a central planner allocating subsidies to competing firms that provide a commodity, with the objective of minimizing its market price, subject to a budget constraint and possibly upper bounds on the total amount that can be allocated to each firm. We consider two types of subsidies, co-payments and technology subsidies. We use a network design under equilibrium flow approach to model an endogenous market response to the subsidy allocation, and obtain structural results and near optimal solutions in various important cases.



Tuesday, 16:15 - 16:40 h, Room: H 0111, Talk 3

Adam Elmachtoub
Supply chain management with online customer selection

Coauthor: Retsef Levi


We consider new online versions of supply chain management and logistics models, where in addition to production decisions, one also has to decide on which customers to serve. Specifically, customers arrive sequentially during a selection phase, and one has to decide whether to accept or reject each customer upon arrival. If a customer is rejected, then a lost-sales cost is incurred. Once the selection decisions are all made, one has to satisfy all the accepted customers with minimum possible production cost. The goal is to minimize the total cost of lost-sales and production. A key feature of the model is that customers arrive in an online manner, and the decision maker does not require any information about future arrivals. We provide several novel algorithms for online customer selection problems which are based on new variants of repeated optimization and interesting connections to cooperative game theory. For many important settings, our algorithms achieve competitive ratio guarantees that are close to best possible.


  signature loans . But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.