Strong Price of Anarchy for Machine Load Balancing (2008)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky
Abstract. As defined by Aumann in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load...
Abstract Online Conflict-Free Coloring for Intervals (2008)
Amos Fiat, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Strong Price of Anarchy for Machine Load Balancing (2008)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky
Abstract. As defined by Aumann in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load...
Strong Price of Anarchy for Machine Load Balancing (2007)
Fiat, Amos, Levy, Meital, Kaplan, Haim, Olonetsky, Svetlana
As defined by Aumann in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load balancing on...
On the price of stability for designing undirected networks with fair cost allocations (2006)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky
Abstract. In this paper we address the open problem of bounding the price of stability for network design with fair cost allocation for undirected graphs posed in [1]. We consider the case where...
Online conflict-free coloring for intervals (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel
Abstract. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Online conflict-free coloring for intervals (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Ji Rí, Matou Sek, ...
Abstract. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the...
On the price of stability for designing undirected networks with fair cost allocations (2006)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, Ronen Shabo
Abstract. In this paper we address the open problem of bounding the price of stability for network design with fair cost allocation for undirected graphs posed in [1]. For the version of this problem...
Online interval coloring and variants (2005)
Abstract. We study interval coloring problems and present new upper and lower bounds for several variants. We are interested in four problems, online coloring of intervals with and without bandwidth...
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...