Publications |
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.
Also presented at Bellairs Workshop on Algorithmic Game Theory, 2009.
[Abstract]
[BiBTeX]
[Paper: PDF, PS]
[Slides: 25min(APPROX)]
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
21st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 319-327, 2009.
[Abstract]
[BiBTeX]
[Paper: PDF, PS]
[Slides: 25min(SPAA)]
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.
@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, PS]
[Slides: 50min, 25min(STOC)]
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, PS]
[Slides: 25min(OPODIS)]
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, PS]
[Slides: 25min(ICALP)]
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
To appear in Theoretical Computer Science (TCS) special issue on WAOA '07.
5th International Workshop on Approximation and Online Algorithms (WAOA), pages 15-26, 2007.
[Abstract]
[BiBTeX]
[Paper: PDF, PS]
[Slides: 25min(WAOA)]
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.
@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
To appear in ACM Transactions on Algorithms (TALG).
19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 320-329, 2007.
[Abstract]
[BiBTeX]
[Paper: PDF, PS]
[Slides: 50min, 25min(SPAA)]
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.
@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, PS]
[Slides: 50min, 25min(STACS)]
[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}}
|
