In the (Unit Demand) Euclidean Capacitated Vehicle Routing problem (CVRP), we are given a collection of \(n\) points in the Euclidean plane (the clients), one extra point (the depot), and one integer \(Q \ge 1\) (the vehicle capacity). A feasible solution is a collection of tours, where each tour contains the depot and at most \(Q\) clients, such that each client belongs to at least one such tour. Our goal is to minimize the total length of the tours. This models, e.g., the problem of delivering identical items stored at the depot to clients using a single vehicle that can carry at most \(Q\) items at a time.

In the Directed Latency problem, we are given an asymmetric metric space (V ∪ {s},c) on a set V of clients and a depot s. We are looking for a path P starting in s that visits all clients and minimizes the sum of the clients’ waiting times (also known as latency) before being visited on the path. This models problems in logistics where client satisfaction is essential, as opposed to objectives like in TSP, where the goal is to make the salesperson as happy as possible.

We present a \(O(\log k)\) -approximation for both the edge-weighted and node-weighted versions of Directed Steiner Tree in planar graphs where \( k \) is the number of terminals. We extend our approach to Multi-Rooted Directed Steiner Tree , in which we get a \(O(R+\log k)\) -approximation for planar graphs for which \( R \) is the number of roots.

We give the first constant-factor approximation algorithm for quasi-bipartite instances of Directed Steiner Tree on graphs that exclude fixed minors. In particular, for $K_r$-minor-free graphs our approximation guarantee is $O(r\cdot\sqrt{\log r})$ and, further, for planar graphs our approximation guarantee is 20. Our algorithm uses the primal-dual scheme. We employ a more involved method of determining when to buy an edge while raising dual variables since, as we show, the natural primal-dual scheme fails to raise enough dual value to pay for the purchased solution. As a consequence, we also demonstrate integrality gap upper bounds on the standard cut-based linear programming relaxation for the Directed Steiner Tree instances we consider.

We present an O(log k)-approximation for both the edge-weighted and node-weighted versions of Directed Steiner Tree in planar graphs where k is the number of terminals. We extend our approach to Multi-Rooted Directed Steiner Tree, in which we get a O(R+log k)-approximation for planar graphs for where R is the number of roots.

k-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.93, even in the plane, if one insists the dependence on k in the running time be polynomial. Without this restriction, a classic algorithm yields a 2^{O((klog k)/{epsilon})}dn-time (1+epsilon)-approximation for Euclidean k-center, where d is the dimension. In this work, we give a faster algorithm for small dimensions: roughly speaking an O^*(2^{O((1/epsilon)^{O(d)} k^{1-1/d} log k)})-time (1+epsilon)-approximation. In particular, the running time is roughly O^*(2^{O((1/epsilon)^{O(1)}sqrt{k}log k)}) in the plane. We complement our algorithmic result with a matching hardness lower bound. We also consider a well-studied generalization of k-center, called Non-uniform k-center (NUkC), where we allow different radii clusters. NUkC is NP-hard to approximate within any factor, even in the Euclidean case. We design a 2^{O(klog k)}n^2 time 3-approximation for NUkC, and a 2^{O((klog k)/epsilon)}dn time (1+\epsilon)-approximation for Euclidean NUkC. The latter time bound matches the bound for k-center.