1,721,062 research outputs found
Competitive algorithms for the bicriteria k-server problem
No full textIn this paper we consider the bicriteria formulation of the well-known online k-server problem where the cost of moving k servers
between given locations is evaluated simultaneously with respect to two different metrics. Every strategy for serving a sequence of
requests is thus characterized by a pair of costs, and an online algorithm is said to be (c1, c2)-competitive in the strong sense if it
is c1-competitive with respect to the first metric and c2-competitive with respect to the second one. We first prove a lower bound
on c1 and c2 that holds for any online bicriteria algorithm for the problem.We then propose an algorithm achieving asymptotically
optimal tradeoffs between the two competitive ratios. Finally, we show how to further decrease the competitive ratios when the two
metrics are induced by the distances in a complete graph and in a path, respectively, obtaining optimal results for particular cases
The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation Is Constant
No full textEfficient offline algorithms for the bicriteria k-server problem and online applications
No full textIn this paper we consider the bicriteria version of the well-known k-server problem in which
the cost incurred by an algorithm is evaluated simultaneously with respect to two different edge
weightings.
We show that it is possible to achieve the same competitive ratios of the previously known online
algorithms with a dramatic improvement of the running time, i.e., from exponential to polynomial.
Such results are obtained by exploiting new polynomial time algorithms able to find offline solutions
whose costs differ from the optimal ones only of additive terms independent from the sequence
of requests
Stackelberg Strategies for Network Design Games
No full textWe consider the Network Design game introduced by Anshelevich et al. [1] in which n source-destination pairs must be connected by n respective players equally sharing the cost of the used links. By considering the classical SUM social function corresponding to the total network cost, it is well known that the price of anarchy for this class of games may be as large as n. One approach for reducing this bound is that of resorting on the Stackelberg model in which for a subset of left perpendicular alpha nright perpendicular coordinated players, with 0 <= alpha <= 1, communication paths inducing better equilibria are fixed. In this paper we show the effectiveness of Stackelberg strategies by providing optimal and nearly optimal bounds on the performance achievable by such strategies. In particular, differently from previous works, we are also able to provide Stackelberg strategies computable in polynomial time and lowering the price of anarchy from n to 2 (1/alpha + 1). Most of the results are extended to the social function MAX, in which the maximum player cost is considered
On the Performances of Nash Equilibria in Isolation Games
No full textWe study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced in [14]. For all the cases in which the existence of Nash equilibria has been shown, we give tight; or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the players' utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases
- …
