I am looking for motivated students who are interested in pursing a graduate degree or internship in the area of approximation algorithms and combinatorial optimization. If interested, please contact me via e-mail.
We present a strengthened version of a lemma due to Bondy and Lovász. This lemma establishes the connectivity of a certain graph whose nodes correspond to the spanning trees of a 2-vertex-connected graph, and implies the k=2 case of the Győri-Lovász Theorem on partitioning of k-vertex-connected graphs. Our strengthened version constructively proves an asymptotically tight O(|V|2) bound on the worst-case diameter of this graph of spanning trees.
Two-way online correlated selection (two-way OCS) is an online algorithm that, at each timestep, takes a pair of elements from the ground set and irrevocably chooses one of the two elements, while ensuring negative correlation in the algorithm's choices. Fahrbach, Huang, Tao, and Zadimoghaddam first invented OCS to solve the edge-weighted online bipartite matching problem, and posed the following tantalizing open question: Can we obtain n-way OCS for n>2, in which the algorithm can be given n>2 elements to choose from at each timestep? In this paper, we affirmatively answer this open question by presenting a three-way OCS.
In the design of real-time systems, it is important to take soft-error tolerance into account. While hardening techniques such as error detection and correction enable us to better tolerate soft-errors, they are inevitably accompanied with execution time overhead. In order to mitigate its impact, Chen et al. proposed to identify the (m,k)-constraints of real-time tasks, which demand that at least m jobs out of k consecutive task invocations must be fault-free, and to design hardening policies based on it. In this paper, we propose a new method to design hardening policies that are adaptive and stochastic. At the heart of our method is a new linear program (LP) formulation that finds an adaptive stochastic policy optimizing the CPU utilization.
We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O(log n / log log n) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on the result of Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi to obtain this guarantee.
Facility location is a prominent optimization problem that has guided a large volume of studies in combinatorial optimization. However, unlike other problems, it was not previously known how this problem behaves in conjunction with parity constraints. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. Although the unconstrained facility location problem as a relaxation for the parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost.
We present a new LP-rounding algorithm for facility location problems, which yields the first constant approximation algorithm for the dynamic facility location problem. This 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. Our algorithm, based on competing exponential clocks, exhibits several properties that distinguish our approach from previous LP-roundings for facility location problems. We demonstrate that these properties enable us to apply our new algorithm to the dynamic problem.
Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In particular, a variety of LP-based methodologies have been applied to and evolved from the uncapacitated facility location problem. Unfortunately, this collection of powerful techniques had not yet been applicable to the more general capacitated facility location problem. In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.
The interaction between the cyber and physical components of CPSs induces delay-workload dependence, creating the unique challenge of power optimization with delay-workload dependence awareness. In this paper, we identify this challenge and present the first formal and comprehensive model to enable rigorous investigations on this topic. We propose a simple power management policy, and show that this policy achieves a best possible notion of optimality. We also experimentally validate the efficiency of our policy.
We present a deterministic (1+√5)/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost between n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints. The present result surpasses the 20-year-old barrier of 5/3 originating from Hoogeveen's analysis of the natural path-variant of Christofides' algorithm. The present techniques can be applied to other optimization problems as well: these applications include the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.
There is a large discrepancy in our understanding of uncapacitated and capacitated versions of network location problems. This paper aims to bridge this discrepancy, by presenting a simple algorithm for the capacitated k-center problem. Our algorithm has a clean analysis that allows us to prove an improved approximation ratio of 9, narrowing down the integrality gap of the standard LP relaxation to either 7, 8, or 9. We present extensions of our techniques to related problems, and also give evidence to show that more powerful preprocessing could lead to better algorithms, by giving an approximation algorithm that beats the integrality gap for instances where all non-zero capacities are uniform.