Michael Elberfeld, Vineet Bafna, Iftah Gamzu, Alexander Medvedovsky, Danny Segev, Dana Silverbush, Uri Zwick and Roded Sharan
On the Approximability of Reachability Preserving Network Orientations
Internet Mathematics (IM), 7(4):209-232, 2011.
[Abstract]
[BiBTeX]
[Paper: PDF]
We introduce a graph orientation problem arising in the study of biological networks. Given
an undirected graph and a list of ordered source-target vertex pairs, the goal is to orient the
graph such that a maximum number of pairs admit a directed source-to-target path. We study
the complexity and approximability of this problem. We show that the problem is NP-hard even
on star graphs and hard to approximate to within some constant factor. On the positive side, we
provide an Ω(loglog n / log n)-factor approximation algorithm for the
problem on n-vertex graphs. We further show that for any instance of the problem there
exists an orientation of the input graph that satisfies a logarithmic fraction of all pairs and
that this bound is tight up to a constant factor. Our techniques also lead to constant factor
approximation algorithms for some restricted variants of the problem.
@article{ElberfeldBGMSSZS11,
author = {Michael Elberfeld and Vineet Bafna and Iftah Gamzu and Alexander Medvedovsky and Danny Segev and Dana Silverbush and Uri Zwick and Roded Sharan},
title = {On the Approximability of Reachability-Preserving Network Orientations},
journal = {Internet Mathematics},
volume = {7},
issue = {4},
year = {2011},
pages = {209-232}}
Yossi Azar, Iftah Gamzu and Ran Roth
Submodular Max-SAT
19th Annual European Symposium on Algorithms (ESA), pages 323-334, 2011.
[Abstract]
[BiBTeX]
[Paper: PDF]
We introduce the submodular Max-SAT problem. This problem is a natural generalization of the
classical Max-SAT problem in which the additive objective function is replaced by a submodular one.
We develop a randomized linear-time 2/3-approximation algorithm for the problem. Our algorithm is
applicable even for the online variant of the problem. We also establish hardness results for both the
online and offline settings. Notably, for the online setting, the hardness result proves that our algorithm
is best possible, while for the offline setting, the hardness result establishes a computational separation
between the classical Max-SAT and the submodular Max-SAT.
@inproceedings{AzarGR11,
author = {Yossi Azar and Iftah Gamzu and Ran Roth},
title = {Submodular Max-SAT},
booktitle = {Proceedings 19th Annual European Symposium on Algorithms},
year = {2011},
pages = {323-334}}
Yossi Azar and Iftah Gamzu
Efficient Submodular Function Maximization under Linear Packing Constraints
Manuscript, 2011.
[Abstract]
[BiBTeX]
[Paper: PDF]
We study the problem of maximizing a monotone submodular set
function subject to linear packing constraints. An instance of
this problem consists of a matrix
A∈[0,1]m×n, a
vector b∈[1,∞)m, and a monotone submodular set
function f:2[n]→R+. The objective is to find
a set S that maximizes f(S) subject to AxS ≤b.
Here, xS stands for the characteristic vector of the set S. A
well-studied special case of this problem is when the objective
function f is linear. This special case captures the class of
packing integer programs.
Our main contribution is an efficient combinatorial algorithm with an approximation
ratio of Ω(1/m1/W), where
W=min{bi /Aij:Aij>0}
is the width of the packing constraints. This result matches the best known performance
guarantee for the linear case. One immediate corollary of this
result is that the algorithm under consideration achieves constant
factor approximation when the number of constraints is constant or
when the width of the packing constraints is sufficiently large.
This motivates us to study the large width setting, trying to
determine its exact approximability. We develop an algorithm that has an approximation
ratio of (1-ε)(1-1/e) when
W=Ω(lnm/ε2). This result (almost) matches
the theoretical lower bound of 1-1/e, which already holds for
maximizing a monotone submodular function subject to a cardinality
constraint.
@article{AzarG11b,
author = {Yossi Azar and Iftah Gamzu},
title = {Efficient Submodular Function Maximization under Linear Packing Constraints},
year = {2011},
note = {Manuscript}}
Yossi Azar and Iftah Gamzu
Ranking with Submodular Valuations
22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1070-1079, 2011.
[Abstract]
[BiBTeX]
[Paper: PDF]
[Slides: 25min]
We study the problem of ranking with submodular valuations. An
instance of this problem consists of a ground set [m], and a
collection of n monotone submodular set functions
f1,...,fn, where each
fi:2[m]→R+.
An additional ingredient of the input is a weight vector
w∈R+n.
The objective is to find a linear ordering of the ground set elements
that minimizes the weighted cover time of the functions. The cover
time of a function is the minimal number of elements in the prefix
of the linear ordering that form a set whose corresponding
function value is greater than a unit threshold value.
Our main contribution is an O(ln(1/ε))-approximation
algorithm for the problem, where ε is the smallest
non-zero marginal value that any function may gain from some
element. Our algorithm orders the elements using an adaptive
residual updates scheme, which may be of independent interest. We
also prove that the problem is Ω(ln(1/ε))-hard to
approximate, unless P=NP. This implies that the outcome of our
algorithm is optimal up to constant factors.
@inproceedings{AzarG11a,
author = {Yossi Azar and Iftah Gamzu},
title = {Ranking with Submodular Valuations},
booktitle = {Proceedings 22nd Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2011},
pages = {1070-1079}}
Iftah Gamzu and Danny Segev
A Polylogarithmic Approximation for Computing Non-Metric Terminal Steiner Trees
Information Processing Letters (IPL), 110(18-19), pages 826-829, 2010.
[Abstract]
[BiBTeX]
[Paper: PDF]
The main contribution of this short note is to provide improved
bounds on the approximability of constructing terminal Steiner
trees in arbitrary undirected graphs. Technically speaking, our
results are obtained by relating this computational task to that
of computing group Steiner trees. As a secondary objective, we
make a concentrated effort to distinguish between the factor by
which constructed trees exceed the optimal backbone cost and
between the deviation from the optimal terminal linking cost.
@article{GamzuS10b,
author = {Iftah Gamzu and Danny Segev},
title = {A Polylogarithmic Approximation for Computing Non-Metric Terminal Steiner Trees},
journal = {Inf. Process. Lett.},
volume = {110},
number = {18-19},
year = {2010},
pages = {826-829}}
Iftah Gamzu, Danny Segev and Roded Sharan
Improved Orientations of Physical Networks
10th International Workshop on Algorithms in Bioinformatics (WABI), pages 215-225, 2010.
[Abstract]
[BiBTeX]
[Paper: PDF]
[Slides: 25min]
The orientation of physical networks is a prime task in
deciphering the signaling-regulatory circuitry of the cell. One
manifestation of this computational task is as a maximum graph
orientation problem, where given an undirected graph with n
vertices and a collection of vertex pairs, the goal is to orient
the edges of the graph so that a maximum number of pairs are
connected by a directed path. We develop an approximation
algorithm for this problem with a performance guarantee of O(log n
/ loglog n). This result improves on a previous logarithmic
approximation, due to Medvedovsky et al. [WABI '08]. In addition,
motivated by interactions whose direction is pre-set such as
protein-DNA interactions, we extend our algorithm to handle mixed
graphs, a major open problem posed by earlier work. In this
setting, we demonstrate that a polylogarithmic approximation ratio
is achievable under biologically-motivated assumptions on the
sought paths.
@inproceedings{GamzuSS10,
author = {Iftah Gamzu and Danny Segev and Roded Sharan},
title = {Improved Orientations of Physical Networks},
booktitle = {Proceedings 10th International Workshop on Algorithms in Bioinformatics},
year = {2010},
pages = {215-225}}
Iftah Gamzu and Danny Segev
A Sublogarithmic Approximation for Highway and Tollbooth Pricing
37th International Colloquium on Automata, Languages and Programming (ICALP), pages 582-593, 2010.
[Abstract]
[BiBTeX]
[Paper: PDF]
[Slides: 50min, 25min]
An instance of the tollbooth problem consists of an undirected
network and a collection of single-minded customers, each of which
is interested in purchasing a fixed path subject to an individual
budget constraint. The objective is to assign a per-unit price to
each edge in a way that maximizes the collective revenue obtained
from all customers. The revenue generated by any customer is equal
to the overall price of the edges in her desired path, when this
cost falls within her budget; otherwise, that customer will not
purchase any edge.
Our main result is a deterministic algorithm for the tollbooth
problem on trees whose approximation ratio is O(log m / loglog
m), where m denotes the number of edges in the underlying
graph. This finding improves on the currently best performance
guarantees for trees, due to Elbassioni et al. [SAGT '09], as well
as for paths (commonly known as the highway problem), due to
Balcan and Blum [EC '06]. An additional interesting consequence is
a computational separation between tollbooth pricing on trees and
the original prototype problem of single-minded unlimited supply
pricing, under a plausible hardness hypothesis due to Demaine et
al. [SODA '06].
@inproceedings{GamzuS10a,
author = {Iftah Gamzu and Danny Segev},
title = {A Sublogarithmic Approximation for Highway and Tollbooth Pricing},
booktitle = {Proceedings 37th International Colloquium on Automata, Languages and Programming},
year = {2010},
pages = {582-593}}
Chandra Chekuri and Iftah Gamzu
Truthful Mechanisms via Greedy Iterative Packing
12th International Workshop on Approximation Algorithms for Combinatorial Problems (APPROX), pages 56-69, 2009.
[Abstract]
[BiBTeX]
[Paper: PDF]
[Slides: 25min]
An important research thread in algorithmic game theory studies
the design of efficient truthful mechanisms that approximate the
optimal social welfare. A fundamental question is whether an
α-approximation algorithm translates into an
α-approximate truthful mechanism. It is well-known that
plugging an α-approximation algorithm into the VCG
technique may not yield a truthful mechanism. Hence, it is natural
to investigate properties of approximation algorithms that enable
their use in truthful mechanisms.
The main contribution of this paper is to identify a useful and
natural property of approximation algorithms, which we call
loser-independence. Intuitively, a loser-independent algorithm
does not change its outcome when the bid of a losing agent
increases, unless that agent becomes a winner. We demonstrate that
loser-independent algorithms can be employed as sub-procedures in
a greedy iterative packing approach while preserving monotonicity.
A greedy iterative approach provides good approximation in the
context of maximizing a non-decreasing submodular function subject
to independence constraints. Our framework gives rise to truthful
approximation mechanisms for various problems. Notably, some
problems arise in online mechanism design.
@inproceedings{ChekuriG09,
author = {Chandra Chekuri and Iftah Gamzu},
title = {Truthful Mechanisms via Greedy Iterative Packing},
booktitle = {Proceedings 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems},
year = {2009},
pages = {56-69}}
Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda and Prasad Raghavendra
Buffer Management for Colored Packets with Deadlines
Theory of Computing Systems (ToCS) special issue on SPAA '09, 49(4):738-756, 2011.
21st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 319-327, 2009.
[Abstract]
[BiBTeX]
[Paper: PDF, PS]
[Slides: 25min]
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.
@article{AzarFGMR11,
author = {Yossi Azar and Uriel Feige and Iftah Gamzu and Thomas Moscibroda and Prasad Raghavendra},
title = {Buffer Management for Colored Packets with Deadlines},
journal = {Theory Comput. Syst.},
volume = {49},
number = {4},
year = {2011},
pages = {738-756}}
@inproceedings{AzarFGMR09,
author = {Yossi Azar and Uriel Feige and Iftah Gamzu and Thomas Moscibroda and Prasad Raghavendra},
title = {Buffer Management for Colored Packets with Deadlines},
booktitle = {Proceedings 21st Annual ACM Symposium on Parallel Algorithms and Architectures},
year = {2009},
pages = {319-327}}
Yossi Azar, Iftah Gamzu and Xiaoxin Yin
Multiple Intents Re-Ranking
41st Annual ACM Symposium on Theory of Computing (STOC), pages 669-678, 2009.
[Abstract]
[BiBTeX]
[Paper: PDF]
[Slides: 50min, 25min]
One of the most fundamental problems in web search is how to
re-rank result web pages based on user logs. Most traditional
models for re-ranking assume each query has a single intent. That
is, they assume all users formulating the same query have similar
preferences over the result web pages. It is clear that this is
not true for a large portion of queries as different users may
have different preferences over the result web pages. Accordingly,
a more accurate model should assume that queries have multiple
intents.
In this paper, we introduce the multiple intents re-ranking
problem. This problem captures scenarios in which some user makes
a query, and there is no information about its real search intent.
In such cases, one would like to re-rank the search results in a
way that minimizes the efforts of all users in finding their
relevant web pages. More formally, the setting of this problem
consists of various types of users, each of which interested in
some subset of the search results. Moreover, each user type has a
non-negative profile vector. Consider some ordering of the
search results. This order determines a position for each search
result, and induces a position vector of the results relevant to
each user type. The overhead of a user type is the dot product of
its profile vector and its induced position vector. The goal is to
order the search results as to minimize the average overhead of
the users.
Our main result is an O(log r)-approximation algorithm for the
problem, where r is the maximum number of search results that
are relevant to any user type. The algorithm is based on a new
technique, which we call harmonic interpolation. In addition, we
consider two important special cases. The first case is when the
profile vector of each user type is non-increasing. This case is a
generalization of the well-known min-sum set cover problem.
We extend the techniques of Feige, Lovasz and Tetali
[Algorithmica '04], and present an algorithm achieving
4-approximation. The second case is when the profile vector of
each user type is non-decreasing. This case generalizes the
minimum latency set cover problem, introduced by Hassin and
Levin [ESA '05]. We devise an LP-based algorithm that attains
2-approximation.
@inproceedings{AzarGY09,
author = {Yossi Azar and Iftah Gamzu and Xiaoxin Yin},
title = {Multiple Intents Re-Ranking},
booktitle = {Proceedings 41st Annual ACM Symposium on Theory of Computing},
year = {2009},
pages = {669-678}}
Yehuda Afek, Iftah Gamzu, Irit Levy, Michael Merritt and Gadi Taubenfeld
Group Renaming
12th International Conference on Principles of Distributed Systems (OPODIS), pages 58-72, 2008.
[Abstract]
[BiBTeX]
[Paper: PDF]
[Slides: 25min]
We study the
group renaming problem, which is a natural
generalization of the
renaming problem. An instance of this
problem consists of
n processors, partitioned into
m groups,
each of at most
g processors. Each processor knows the name of
its group, which is in {
1,…,M}. The task of each
processor is to choose a new name for its group such that
processors from different groups choose different new names from
{
1,…,l}, where
l <
M. We consider two variants
of the problem: a
tight variant, in which processors of the
same group must choose the same new group name, and a
loose
variant, in which processors from the same group may choose
several different names. Our findings can be briefly summarized as
follows:
- We present an algorithm that solves the tight variant of the
problem with l = 2m-1 in a system consisting of
g-consensus objects and atomic read/write registers. In
addition, we prove that it is impossible to solve this problem in
a system having only (g-1)-consensus objects and atomic read/write
registers.
- We devise an algorithm for the loose variant of the problem
that only uses atomic read/write registers, and has
l = 3n-√n-1.
The algorithm also guarantees that the number of
different new group names chosen by processors from the same group
is at most min{g, 2m, 2√n}. Furthermore, we consider
the special case when the groups are uniform in size and show that
our algorithm is self-adjusting to have l = m(m+1)/2, when
m < √n, and l = 3n/2+m-√n/2-1,
otherwise.
@inproceedings{AfekGLMT08,
author = {Yehuda Afek and Iftah Gamzu and Irit Levy and Michael Merritt and Gadi Taubenfeld},
title = {Group Renaming},
booktitle = {Proceedings 12th International Conference on Principles of Distributed Systems},
year = {2008},
pages = {58-72}}
Yossi Azar and Iftah Gamzu
Truthful Unification Framework for Packing Integer Programs with Choices
35th International Colloquium on Automata, Languages and Programming (ICALP), pages 833-844, 2008.
[Abstract]
[BiBTeX]
[Paper: PDF]
[Slides: 25min]
One of the most interesting research directions within the field
of algorithmic mechanism design revolves the study of hard
combinatorial optimization problems. In this setting, many common
techniques, which are broadly used by approximation algorithms,
cannot be utilized as they violate certain monotonicity properties
that are imperative for truthfulness. Consequently, it seems of
the essence to develop alternative algorithmic methods, which can
underlie truthful mechanisms. In particular, since many hard
optimization problems can be formulated as instances of integer
linear programs, it seems that devising techniques that apply to
integer linear programs is significantly important. This
perception reinforces by the observation that one of the most
general and efficient ways to approximately solve such programs,
which is linear programming-based randomized rounding, generally
fails to be monotone.
In this paper, we focus our attention on packing integer programs,
and packing integer programs with choices. Our main findings can
be briefly summarized as follows:
- We develop a framework, which can be used as a building
block to approximately solve packing integer programs and packing
integer programs with choices. The framework is built upon a
unification technique that approximately solves an instance of a
packing integer program with choices, given algorithms that
approximately solve sub-instances of it. The framework is
deterministic and monotone, and hence can underlie truthful
deterministic mechanisms.
- We demonstrate the applicability of the framework by
employing it to several NP-hard problems. In particular,
we focus on the bandwidth allocation problem in
tree networks, and the multiple knapsack problem on
bipartite graphs. Notably, using the mentioned framework, we
attain the first non-trivial approximation guarantees for these
problems in a game theoretic setting.
@inproceedings{AzarG08,
author = {Yossi Azar and Iftah Gamzu},
title = {Truthful Unification Framework for Packing Integer Programs with Choices},
booktitle = {Proceedings 35th International Colloquium on Automata, Languages and Programming},
year = {2008},
pages = {833-844}}
Iftah Gamzu
Improved Lower Bounds for Non-Utilitarian Truthfulness
Theoretical Computer Science (TCS) special issue on WAOA '07, 412(7):626-632, 2011.
5th International Workshop on Approximation and Online Algorithms (WAOA), pages 15-26, 2007.
[Abstract]
[BiBTeX]
[Paper: PDF]
[Slides: 25min]
One of the most fundamental results in the field of mechanism
design states that every utilitarian social choice function admits
a mechanism that truthfully implements it. In stark contrast with
this finding, when one considers a non-utilitarian social choice
function, it turns out that no guarantees can be made, i.e. there
are non-utilitarian functions, which cannot be truthfully
implemented. In light of this state of affairs, one of the most
natural and intriguing objectives of research is to understand the
inherent limitations in the infrastructure of truthful mechanisms
for non-utilitarian social choice functions.
In this paper, we focus our attention on studying the boundaries
imposed by truthfulness for two non-utilitarian multi-parameter
optimization problems. The first is the
workload
minimization in inter-domain routing problem, which models one of
the most principle problems in the design of routing protocols,
and the other is the
unrelated machines scheduling problem,
which is one of the most classical and general variants in the
field of scheduling. Our main findings can be briefly summarized
as follows:
- We prove that any truthful deterministic mechanism, and any
universal truthful randomized mechanism for the workload
minimization in inter-domain routing problem cannot achieve an
approximation guarantee that is better than 2. These results
improve the current lower bounds of (1+√5)/2 ≈
1.618 and (3 + √5)/4 ≈ 1.309, which are due to
Mu'alem and Schapira [SODA '07].
- We establish a lower bound of 1+√2 ≈ 2.414
on the achievable approximation ratio of any truthful
deterministic mechanism for the unrelated machines scheduling
problem when the number of machines is at least 3. This lower
bound is comparable to a recent result by Christodoulou,
Koutsoupias and Vidali [SODA '07]. Nevertheless, our approach is
considerably simpler, and thus may shed some new light on the
foundations of this problem.
@article{Gamzu11,
author = {Iftah Gamzu},
title = {Improved Lower Bounds for Non-Utilitarian Truthfulness,
journal = {Theor. Comput. Sci.},
volume = {412},
number = {7},
year = {2011},
pages = {626-632}}
@inproceedings{Gamzu07,
author = {Iftah Gamzu},
title = {Improved Lower Bounds for Non-Utilitarian Truthfulness},
booktitle = {Proceedings 5th International Workshop on Approximation and Online Algorithms},
year = {2007},
pages = {15-26}}
Yossi Azar, Iftah Gamzu and Shai Gutner
Truthful Unsplittable Flow for Large Capacity Networks
ACM Transactions on Algorithms (TALG), 6(2):36, 2010.
19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 320-329, 2007.
[Abstract]
[BiBTeX]
[Paper: PDF]
[Slides: 50min, 25min]
The unsplittable flow problem is one of the most
extensively studied optimization problems in the field of
networking. An instance of it consists of an edge capacitated
graph and a set of connection requests, each of which is
associated with source and target vertices, a demand, and a value.
The objective is to route a maximum value subset of requests
subject to the edge capacities. It is a well known fact that as
the capacities of the edges are larger with respect to the maximal
demand among the requests, the problem can be approximated better.
In particular, it is known that for sufficiently large capacities,
the integrality gap of the corresponding integer linear program
becomes 1+ε, which can be matched by an algorithm that
utilizes the randomized rounding technique.
In this paper, we focus our attention on the large capacities
unsplittable flow problem in a game theoretic setting. In this
setting, there are selfish agents, which control some of the
requests characteristics, and may be dishonest about them. It is
worth noting that in game theoretic settings many standard
techniques, such as randomized rounding, violate certain
monotonicity properties, which are imperative for truthfulness,
and therefore cannot be employed. In light of this state of
affairs, we design a monotone deterministic algorithm, which is
based on a primal-dual machinery, which attains an approximation
ratio of e/(e-1), up to a disparity of ε away.
This implies an improvement on the current best truthful
mechanism, as well as an improvement on the current best
combinatorial algorithm for the problem under consideration.
Surprisingly, we demonstrate that any algorithm in the family of
reasonable iterative path minimizing algorithms, cannot yield a
better approximation ratio. Consequently, it follows that in order
to achieve a monotone PTAS, if exists, one would have to exert
different techniques. We also consider the large capacities
single-minded multi-unit combinatorial auction problem.
This problem is closely related to the unsplittable flow problem
since one can formulate it as a special case of the integer linear
program of the unsplittable flow problem. Accordingly, we obtain a
comparable performance guarantee by refining the algorithm
suggested for the unsplittable flow problem.
@article{AzarGG10,
author = {Yossi Azar and Iftah Gamzu and Shai Gutner},
title = {Truthful Unsplittable Flow for Large Capacity Networks},
journal = {ACM Transactions on Algorithms},
volume = {6},
number = {2},
year = {2010}}
@inproceedings{AzarGG07,
author = {Yossi Azar and Iftah Gamzu and Shai Gutner},
title = {Truthful Unsplittable Flow for Large Capacity Networks},
booktitle = {Proceedings 19th Annual ACM Symposium on Parallel Algorithms and Architectures},
year = {2007},
pages = {320-329}}
Iftah Gamzu and Danny Segev
Improved Online Algorithms for the Sorting Buffer Problem on Line Metrics
ACM Transactions on Algorithms (TALG), 6(1):15, 2009.
24th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 658-669, 2007.
[Abstract]
[BiBTeX]
[Paper: PDF]
[Slides: 50min, 25min]
[Poster]
An instance of the
sorting buffer problem consists of a
metric space and a server, equipped with a finite-capacity buffer
capable of holding a limited number of requests. An additional
ingredient of the input is an online sequence of requests, each of
which is characterized by a destination in the given metric;
whenever a request arrives, it must be stored in the sorting
buffer. At any point in time, a currently pending request can be
served by drawing it out of the buffer and moving the server to
its corresponding destination. The objective is to serve all input
requests in a way that minimizes the total distance traveled by
the server.
In this paper, we focus our attention on instances of the problem
in which the underlying metric is either an
evenly-spaced
line metric or a
continuous line metric. Although such
restricted settings may appear to be very simple at first glance,
we demonstrate that they still capture one of the most fundamental
problems in the design of storage systems, known as the
disk
arm scheduling problem. Our main findings can be briefly
summarized as follows:
- We present a deterministic O(log n)-competitive
algorithm for n-point evenly-spaced line metrics. This result
improves over a randomized O(log2n)-competitive algorithm
due to Khandekar and Pandit [STACS '06]. It also refutes their conjecture,
stating that a deterministic strategy is unlikely to obtain a
non-trivial competitive ratio. It also refutes their
conjecture, stating that it is unlikely to obtain a non-trivial competitive ratio deterministically.
- We devise a deterministic O(logN loglogN)-competitive
algorithm for continuous line metrics, where N
denotes the length of the input sequence. In this context, we
introduce a novel discretization technique, which is of
independent interest, as it may be applicable in other settings as
well.
- We establish the first non-trivial lower bound for the
evenly-spaced case, by proving that the competitive ratio of any
deterministic algorithm is at least (5+3√3)/(3+√3) ≈ 2.154.
This result settles, to some extent, an
open question due to Khandekar and Pandit [STACS '06], who posed
the task of attaining lower bounds on the achievable competitive
ratio as a foundational objective for future research.
@article{GamzuS09,
author = {Iftah Gamzu and Danny Segev},
title = {Improved Online Algorithms for the Sorting Buffer Problem on Line Metrics},
journal = {ACM Transactions on Algorithms},
volume = {6},
number = {1},
year = {2009}}
@inproceedings{GamzuS07,
author = {Iftah Gamzu and Danny Segev},
title = {Improved Online Algorithms for the Sorting Buffer Problem},
booktitle = {Proceedings 24th International Symposium on Theoretical Aspects of Computer Science},
year = {2007},
pages = {658-669}}
