We consider the deterministic inventory routing problem over a discrete finite time horizon. Given clients on a metric, each with daily demands that must be delivered from a depot and holding costs over the planning horizon, an optimal solution selects a set of daily tours through a subset of clients to deliver all demands before they are due and minimizes the total holding and tour routing costs over the horizon. In the capacitated case, a limited number of vehicles are available, where each vehicle makes at most one trip per day. Each trip from the depot is allowed to carry a limited amount of supply to deliver. We develop fast heuristics for both cases by solving a family of prize-collecting Steiner tree instances. Computational experiments show our heuristics can find near-optimal solutions for both cases and substantially reduce the runtime compared with a pure mixed integer programming formulation approach.

We study a fundamental class of two-layer network design problems. A hub layer is configured by establishing hubs at selected nodes at considerable cost so that the routes between hubs can be operated cheaply. The remaining edges in the network are operated at regular cost. The resulting problem is to determine the set of nodes to open hubs and the set of edges to establish in order to find a network of minimum total cost. We consider the case where the network is required to form a Steiner tree spanning a given set of terminal vertices. When edge costs are non-metric, we show logarithmic approximation hardness even for the special case of spanning trees. On the other hand, we show a polynomial-time reduction for Steiner trees to its corresponding node-weighted version thus proving a logarithmic approximation factor. When edge costs are metric, we show the problem is only a constant factor harder to approximate than its original version (with no hub installation) using a similar reduction.

The problem of chasing convex functions is easy to state: faced with a sequence of convex functions f t over d-dimensional Euclidean spaces, the goal of the algorithm is to output a point x t at each time, so that the sum of the function costs f t (x t ), plus the movement costs ||x t − x t − 1 || is minimized. This problem generalizes questions in online algorithms such as caching and the k-server problem. In 1994, Friedman and Linial posed the question of getting an algorithm with a competitive ratio that depends only on the dimension d. In this talk we give an O (d)-competitive algorithm, based on the notion of the Steiner point of a convex body.

We study the problem of chasing convex bodies online: given a sequence of convex bodies the algorithm must respond with points in an online fashion (i.e., is chosen before is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a -competitive algorithm for this problem. We give an algorithm that is -competitive for any sequence of length .

We study the problem of chasing convex bodies online: given a sequence of convex bodies Kt ⊆ ℝd the algorithm must respond with points xt ϵ Kt in an on-line fashion (i.e., xt is chosen before Kt+1 is revealed). The objective is to minimize the total distance between successive points in this sequence. Recently, Bubeck et al. (STOC 2019) gave a 2O(d)-competitive algorithm for this problem. We give an algorithm that is -competitive for any sequence of length T.

We study Stackelberg Security Games where the defender, in addition to allocating defensive resources to protect targets from the attacker, can strategically manipulate the attacker’s payoff under budget constraints in weighted L^p-norm form regarding the amount of change. For the case of weighted L^1-norm constraint, we present (i) a mixed integer linear program-based algorithm with approximation guarantee; (ii) a branch-and-bound based algorithm with improved efficiency achieved by effective pruning; (iii) a polynomial time approximation scheme for a special but practical class of problems. In addition, we show that problems under budget constraints in L^0 and weighted L^\infty-norm form can be solved in polynomial time.