Publication
Improving Christofides' Algorithm for the s-t Path TSP
Related publications (43)
Dynamic Facility Location via Exponential Clocks
Ola Nils Anders Svensson, Ashkan Norouzi Fard, Hyung Chan An
The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance ...
Association for Computing Machinery2017Centrality of trees for capacitated -center
Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara
We consider the capacitated -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) locations (called centers) and assign each ...
Springer Heidelberg2015Optimal Hybrid Perimeter and Switching Plans Control for Urban Traffic Networks
Nikolaos Geroliminis, Jack Haddad, Mohammadreza Hajiahmadi
Since centralized control of urban networks with detailed modeling approaches is computationally complex, developing efficient hierarchical control strategies based on aggregate modeling is of great importance. The dynamics of a heterogeneous large-scale u ...
Institute of Electrical and Electronics Engineers2015Approximation algorithms for regret minimization in vehicle routing problems
In this thesis, we present new approximation algorithms as well as hardness of approximation results for NP-hard vehicle routing problems related to public transportation. We consider two different problem classes that also occur frequently in areas such a ...
EPFL2014Centrality of Trees for Capacitated k-Center
Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara
We consider the capacitated k-center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) k locations (called centers) and assign e ...
Springer2014Node-weighted network design and maximum sub-determinants
We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~. Then, we draw a connection to Goem ...
EPFL2014New Results in the Theory of Linear and Integer Programming
The polynomial Hirsch conjecture states that the vertex-edge diameter of a d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. For the special case where the polyhedron is defined as the set of points satisfying a system Ax ≤ b of ...
EPFL2012