1,721,056 research outputs found
On the bicriteria k-server problem
No full textIn this article we consider multicriteria formulations of classical online problems in which
an algorithm must simultaneously perform well with respect to two different cost measures. Every
strategy for serving a sequence of requests is characterized by a pair of costs and therefore there can
be many different minimal or optimal incomparable solutions. The adversary is assumed to choose
from one of these minimal strategies and the performance of the algorithm is measured with respect
to the costs the adversary pays servicing the sequence according to its determined choice of strategy.
We consider a parametric family of functions which includes all the possible selections for such
strategies. Then, starting from a simple general method that combines any multicriteria instance
into a single-criterion one, we provide a universal multicriteria algorithm that can be applied to
different online problems. In the multicriteria k-server formulationwith two different edge weightings,
for each function class, such a universal algorithm achieves competitive ratios that are only an
O(logW) multiplicative factor away from the corresponding determined lower bounds, where W is
the maximum ratio between the two weights associated to each edge. We then extend our results to
two specific functions, for which nearly optimal competitive algorithms are obtained by exploiting
more knowledge of the selection properties. Finally, we show how to apply our framework to other
multicriteria online problems sharing similar properties
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
Exact algorithms for a discrete metric labeling problem
No full textWe are given a edge-weighted undirected graph G = (V, E) and a set of labels/colors C = {1, 2, . . . , p}. A non-empty subset
C_v in C is associated with each vertex v in V. A coloring of the vertices is feasible if each vertex v is colored with a color of C_v. A
coloring uniquely defines a subset E_0 in E of edges having different colored endpoints. The problem of finding a feasible coloring
which defines a minimum weight E_0 is, in general, NP-hard. In this work we first propose polynomial time algorithms for some
special cases, namely when the input graph is a tree, a cactus or with bounded tree-width. Then, an implicit enumeration scheme
for finding an optimal coloring in the general case is described and computational results are presented
- …
