Graphs with bounded highway dimension were introduced by Abraham et al. [ Proceedings of SODA 2010, pp. 782--793] as a model of transportation networks. We show that any such graph can be embedded into a distribution over bounded treewidth graphs with arbitrarily small distortion. More concretely, given a weighted graph $G=(V,E)$ of constant highway dimension, we show how to randomly compute a weighted graph $H=(V,E')$ that distorts shortest path distances of $G$ by at most a $1+\varepsilon$ factor in expectation, and whose treewidth is polylogarithmic in the aspect ratio of $G$. Our probabilistic embedding implies quasi-polynomial time approximation schemes for a number of optimization problems that naturally arise in transportation networks, including Travelling Salesman, Steiner Tree, and Facility Location. To construct our embedding for low highway dimension graphs we extend Talwar's [ Proceedings of STOC 2004, pp. 281--290] embedding of low doubling dimension metrics into bounded treewidth graphs, which generalizes known results for Euclidean metrics. We add several nontrivial ingredients to Talwar's techniques, and in particular thoroughly analyze the structure of low highway dimension graphs. Thus we demonstrate that the geometric toolkit used for Euclidean metrics extends beyond the class of low doubling metrics.

We consider various multi-vehicle versions of the minimum latency problem. There is a fleet of k vehicles located at one or more depot nodes, and we seek a collection of routes for these vehicles that visit all nodes so as to minimize the total latency incurred, which is the sum of the client waiting times. We obtain an 8.497-approximation for the version where vehicles may be located at multiple depots and a 7.183-approximation for the version where all vehicles are located at the same depot, both of which are the first improvements on this problem in a decade. Perhaps more significantly, our algorithms exploit various LP relaxations for minimum-latency problems. We show how to effectively leverage two classes of LPs—configuration LPs and bidirected LP relaxations—that are often believed to be quite powerful but have only sporadically been effectively leveraged for network-design and vehicle-routing problems. This gives the first concrete evidence of the effectiveness of LP relaxations for this class of problems. The 8.497-approximation the multiple-depot version is obtained by rounding a near-optimal solution to an underlying configuration LP for the problem. The 7.183-approximation can be obtained both via rounding a bidirected LP for the single-depot problem or via more combinatorial means. The latter approach uses a bidirected LP to obtain the following key result that is of independent interest: for any k, we can efficiently compute a rooted tree that is at least as good, with respect to the prize-collecting objective (i.e., edge cost + number of uncovered nodes) as the best collection of k rooted paths. This substantially generalizes a result of Chaudhuri et al. [11] for k = 1, yet our proof is significantly simpler. Our algorithms are versatile and extend easily to handle various extensions involving: (i) weighted sum of latencies, (ii) constraints specifying which depots may serve which nodes, (iii) node service times. Finally, we propose a configuration LP that sheds further light on the power of LP relaxations for minimum-latency problems. We prove that the integrality gap of this LP is at most 3.592, even for the multi-depot problem, both via an efficient rounding procedure, and by showing that it is at least as powerful as a stroll-based lower bound that is oft-used for minimum-latency problems; the latter result implies an integrality gap of at most 3.03 when k = 1. Although, we do not know how to solve this LP in general, it can be solved (near-optimally) when k = 1, and this yields an LP-relative 3.592-approximation for the single-vehicle problem, matching (essentially) the current-best approximation ratio for this problem.

We prove that no online algorithm (even randomized, against an oblivious adversary) is better than 1/2-competitive for welfare maximization with coverage valuations, unless NP = RP. Since the Greedy algorithm is known to be 1/2-competitive for monotone submodular valuations, of which coverage is a special case, this proves that Greedy provides the optimal competitive ratio. On the other hand, we prove that Greedy in a stochastic setting with i.i.d. items and valuations satisfying diminishing returns is (1 − 1/e)-competitive, which is optimal even for coverage valuations, unless NP = RP. For online budget-additive allocation, we prove that no algorithm can be 0.612-competitive with respect to a natural LP which has been used previously for this problem.

We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (MDPs) regardless of the discount factor. For a deterministic MDP with n states and m actions, we prove the simplex method runs in O(n3m2 log2 n) iterations if the discount factor is uniform and O(n5m3 log2 n) iterations if each action has a distinct discount factor. Previously the simplex method was known to run in polynomial time only for discounted MDPs where the discount was bounded away from 1 [Ye11]. Unlike in the discounted case, the algorithm does not greedily converge to the optimum, and we require a more complex measure of progress. We identify a set of layers in which the values of primal variables must lie and show that the simplex method always makes progress optimizing one layer, and when the upper layer is updated the algorithm makes a substantial amount of progress. In the case of nonuniform discounts, we define a polynomial number of “milestone” policies and we prove that, while the objective function may not improve substantially overall, the value of at least one dual variable is always making progress towards some milestone, and the algorithm will reach the next milestone in a polynomial number of steps.

Credit networks represent a way of modeling trust between entities in a network. Nodes in the network print their own currency and trust each other for a certain amount of each other's currency. This allows the network to serve as a decentralized payment infrastructure---arbitrary payments can be routed through the network by passing IOUs between trusting nodes in their respective currencies---and obviates the need for a common currency. Nodes can repeatedly transact with each other and pay for the transaction using trusted currency. A natural question to ask in this setting is: how long can the network sustain liquidity, i.e. how long can the network support the routing of payments before credit dries up? We answer this question in terms of the long term failure probability of transactions for various network topologies and credit values.

We study the single-sink buy-at-bulk problem with an unknown cost function. We wish to route flow from a set of demand nodes to a root node, where the cost of routing x total flow along an edge is proportional to f(x) for some concave, non-decreasing function f satisfying f(0)=0. We present a simple, fast, combinatorial algorithm that takes a set of demands and constructs a single tree T such that for all f the cost f(T) is a 47.45-approximation of the optimal cost for that f. This is within a factor of 2.33 of the best approximation ratio currently achievable when the tree can be optimized for a specific function. Trees achieving simultaneous O(1)-approximations for all concave functions were previously not known to exist regardless of computation time.

We consider the single-source (or single-sink) buy-at-bulk problem with an unknown concave cost function. We want to route a set of demands along a graph to or from a designated root node, and the cost of routing x units of flow along an edge is proportional to some concave, non-decreasing function f such that f(0) = 0. We present a polynomial time algorithm that finds a distribution over trees such that the expected cost of a tree for any f is within an O(1)-factor of the optimum cost for that f. The previous best simultaneous approximation for this problem, even ignoring computation time, was O(log |D|), where D is the multi-set of demand nodes. We design a simple algorithmic framework using the ellipsoid method that finds an O(1)-approximation if one exists, and then construct a separation oracle using a novel adaptation of the Guha, Meyerson, and Munagala algorithm for the single-sink buy-at-bulk problem that proves an O(1) approximation is possible for all f. The number of trees in the support of the distribution constructed by our algorithm is at most 1+log |D|.