Polynomially testable characterization of cost matrices associated with a complete digraph on $n$ nodes such that all the Hamiltonian cycles (tours) have the same cost is well known. Tarasov~\cite{TARA81} obtained a characterization of cost matrices where tour costs take two distinct values. We provide a simple alternative characterization of such cost matrices that can be … Read more
We introduce and study the batched bin packing problem (BBPP), a bin packing problem in which items become available for packing incrementally, one batch at a time. A batched algorithm must pack a batch before the next batch becomes known. A batch may contain several items; the special case when each batch consists of merely … Read more
In the recently published book on the Traveling Salesman Problem, half of Chapter 6 is devoted to domination analysis (DA) of heuristics for the Traveling Salesman Problem. Another chapter (in preparation) is a detailed overview of the whole area of DA. Both chapters are of considerable length. The purpose of this paper is to give … Read more
We present a multi-exchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between $3+2\sqrt{2}-\epsilon$ and $3+2\sqrt{2}+\epsilon$ for any given constant … Read more
We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith’s ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms. Citation Working Paper 4435-03, Sloan … Read more
Let $P$ be a combinatorial optimization problem, and let $A$ be an approximation algorithm for $P$. The domination ratio $\domr(A,s)$ is the maximal real $q$ such that the solution $x(I)$ obtained by $A$ for any instance $I$ of $P$ of size $s$ is not worse than at least the fraction $q$ of the feasible solutions … Read more
We propose a {\em quasi-greedy} algorithm for approximating the classical uncapacitated $2$-level facility location problem ($2$-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the minimization $2$-LFLP problem, in an interesting way, to the maximization version of the single level facility location problem. Another feature of … Read more
Virtual private networks (VPN) are often used to distribute live content, such as video or audio streams, from a single source to a large number of destinations. Streaming caches or splitters are deployed in these multicast networks to allow content distribution without overloading the network. In this paper, we consider two combinatorial optimization problems that … Read more
We provide a characterization of the cases when the greedy algorithm may produce the unique worst possible solution for the problem of finding a minimum weight base in a uniform independence system when the weights are taken from a finite range. We apply this theorem to TSP and the minimum bisection problem. The practical message … Read more
In this paper, we consider a class of quadratic maximization problems. One important instance in that class is the famous quadratic maximization formulation of the max-cut problem studied by Goemans and Williamson. Since the problem is NP-hard in general, following Goemans and Williamson, we apply the approximation method based on the semidefinite programming (SDP) relaxation. … Read more