Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of
n
weighted vertices and ...a
k
-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper
k
-coloring of the vertices. The cost of recoloring a vertex is the vertex’s weight. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm. We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an
O
(
log
n
)
-competitive deterministic algorithm and an
Ω
(
log
n
)
lower bound on the competitive ratio of randomized algorithms. For
(
Δ
+
1
)
-coloring, where
Δ
is the maximal node degree, we present tight bounds of
Θ
(
Δ
)
and
Θ
(
log
Δ
)
on the competitive ratios of deterministic and randomized algorithms, respectively (where
Δ
denotes the maximum degree). We also consider the fully dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are arbitrarily weighted, and all our lower bounds hold even in the uniform weights (unweighted) case.
We discuss one of the most fundamental scheduling problem of processing jobs on a single machine to minimize the weighted flow time (weighted response time). Our main result is a O(log P)-competitive ...algorithm, where P is the maximum-to-minimum processing time ratio, improving upon the O(log^2 P)-competitive algorithm of Chekuri, Khanna and Zhu (STOC 2001). We also design a O(log D)-competitive algorithm, where D is the maximum-to-minimum density ratio of jobs. Finally, we show how to combine these results with the result of Bansal and Dhamdhere (SODA 2003) to achieve a O(log(min(P, D, W)))-competitive algorithm (where W is the maximum-to-minimum weight ratio), without knowing P, D, W in advance. As shown by Bansal and Chan (SODA 2009), no constant-competitive algorithm is achievable for this problem.
We consider buffer management of unit packets with deadlines for a multi-port device with reconfiguration overhead. The goal is to maximize the throughput of the device, i.e., the number of packets ...delivered by their deadline. For a single port or with free reconfiguration, the problem reduces to the well-known packets scheduling problem, where the celebrated earliest-deadline-first (EDF) strategy is optimal 1-competitive. However, EDF is not 1-competitive when there is a reconfiguration overhead. We design an online algorithm that achieves a competitive ratio of 1−
o
(1) when the ratio between the minimum laxity of the packets and the number of ports tends to infinity. This is one of the rare cases where one can design an almost 1-competitive algorithm. One ingredient of our analysis, which may be interesting on its own right, is a perturbation theorem on EDF for the classical packets scheduling problem. Specifically, we show that a small perturbation in the release and deadline times cannot significantly degrade the optimal throughput. This implies that EDF is robust in the sense that its throughput is close to the optimum even when the deadlines are not precisely known.
We investigate the influence of different algorithmic choices on the approximation ratio in selfish scheduling. Our goal is to design local policies that minimize the inefficiency of resulting ...equilibria. In particular, we design optimal coordination mechanisms for unrelated machine scheduling, and improve the known approximation ratio from Θ(
m
) to Θ(log
m
), where
m
is the number of machines.
A
local
policy for each machine orders the set of jobs assigned to it only based on parameters of those jobs. A
strongly local
policy only uses the processing time of
jobs on the same machine. We prove that the approximation ratio of any set of strongly local ordering policies in equilibria is at least Ω(
m
). In particular, it implies that the
approximation ratio of a greedy shortest-first algorithm for machine scheduling is at least Ω(
m
). This closes the gap between the known lower and upper bounds for this problem and
answers an open question raised by Ibarra and Kim (1977) Ibarra OH, Kim CE (1977) Heuristic algorithms for scheduling independent
tasks on nonidentical processors.
J. ACM
24(2):280–289., and Davis and Jaffe (1981) Davis E, Jaffe JM (1981) Algorithms for scheduling tasks on unrelated
processors.
J. ACM
28(4):721–736.. We then design a local ordering policy with the approximation ratio of Θ(log
m
) in equilibria, and prove that this policy is optimal among all local ordering policies. This policy orders the jobs in the nondecreasing order of their inefficiency, i.e., the ratio between the processing time on that machine over the minimum processing time. Finally, we show that best responses of players for the inefficiency-based policy may not converge to a pure Nash equilibrium, and present a Θ(log
2
m
) policy for which we can prove fast convergence of best responses to pure Nash equilibria.
In their seminal work 8, Lenstra, Shmoys, and Tardos proposed a 2-approximation algorithm to solve the problem of scheduling jobs on unrelated parallel machines with the objective of minimizing ...makespan. In contrast to their model, where a job is processed to completion by scheduling it on any one machine, we consider the scenario where each job j requires processing on kj different machines, independently. For this generalization, we propose a 2-approximation algorithm based on the ρ-relaxed decision procedure 8 and open cycles used in 3,2.
•Makespan minimization on unrelated parallel machines.•Generalization: job may require processing on multiple machines, independently.•Argue LST algorithm cannot be extended for this generalization.•2-Approximation algorithm combining a 2-relaxed decision procedure and open cycles.
We study an online version of linear Fisher market. In this market there are
m
buyers and a set of
n
dividable goods to be allocated to the buyers. The utility that buyer
i
derives from good
j
is
u
i
...j
. Given an allocation
U
^
in which buyer
i
has utility
U
^
i
we study a quality measure that is based on taking an average of the ratios
U
i
/
U
^
i
with respect to any other allocation
U
. Market equilibrium allocation is the optimal solution with respect to this measure. Our setting is online and so the allocation of each good should be done without any knowledge of the upcoming goods. We design an online algorithm for the problem that is only worse by a logarithmic factor than any other solution with respect to this quality measure, and in particular competes with the market equilibrium allocation. We prove a tight lower bound which shows that our algorithm is optimal up to constants. Our algorithm uses a primal dual convex programming scheme. To the best of our knowledge this is the first time that such a scheme is used in the online framework.
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city ...has an attached demand specifying the number of brushes that can be sold in that city. What is the best route to take to sell the quota while traveling the least distance possible? Notice that unlike the standard traveling salesman problem, not only do we need to figure out the order in which to visit the cities, but we must decide the more fundamental question: which cities do we want to visit? In this paper we give the first approximation algorithm having a polylogarithmic performance guarantee for this problem, as well as for the slightly more general "prize-collecting traveling salesman problem" (PCTSP) of Balas, and a variation we call the "bank robber problem" (also called the "orienteering problem" by Golden, Levi, and Vohra). We do this by providing an O(log2k) approximation to the somewhat cleaner k-MST problem which is defined as follows. Given an undirected graph on n nodes with nonnegative edge weights and an integer $k \leq n$, find the tree of least weight that spans k vertices. (If desired, one may specify in the problem a "root vertex" that must be in the tree as well.) Our result improves on the previous best bound of $O(\sqrt{k})$ of Ravi et al.
PDF
