All types (
28 )
agt (
6 )
approximation (
8 )
Conference (
19 )
Journal (
15 )
network (
12 )
Preprint (
3 )
probability (
7 )

Sort by year:

Hypercongestionâ€”the phenomenon that higher traffic densities can reduce throughputâ€”is well understood at the link level, but has also been observed in a macroscopic form at the level of traffic networks; for instance, in morning rush-hour traffic into a downtown core. In this paper, we show that macroscopic hypercongestion can occur as a purely emergent effect of dynamic equilibrium behaviour on a network, even if the underlying link dynamics (we consider Vickrey bottlenecks with spaceless vertical queues) do not exhibit hypercongestion.

We give new approximation algorithms for the submodular joint replenishment problem and the inventory routing problem, using an iterative rounding approach. In both problems, we are given a set of *N* items and a discrete time horizon of *T* days in which given demands for the items must be satisfied. Ordering a set of items incurs a cost according to a set function, with properties depending on the problem under consideration. Demand for an item at time *t* can be satisfied by an order on any day prior to *t*, but a holding

cost is charged for storing the items during the intermediate period; the goal is to minimize the sum of the ordering and holding cost. Our approximation factor for both problems is *O*(log log min(*N,T*)); this

improves exponentially on the previous best results.