• Competitive algorithms for the...

Result: Competitive algorithms for the bicriteria k-server problem

Title:
Competitive algorithms for the bicriteria k-server problem
Authors:
FLAMMINI, Michele, NICOSIA, Gaia
Source:
International Symposium on Combinatorial Optimization CO'02Discrete applied mathematics. 154(15):2117-2127
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2006.
Publication Year:
2006
Physical Description:
print, 16 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Optimisation. Problèmes de recherche, Optimization. Search problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Logiciel, Software, Performances des systèmes informatiques. Fiabilité, Computer systems performance. Reliability, Algorithme compétitif, Competitive algorithms, Algorithme en ligne, Online algorithm, Algoritmo en línea, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Borne inférieure, Lower bound, Cota inferior, Chemin graphe, Graph path, Camino grafo, Chemin optimal, Optimal path, Camino óptimo, Compétitivité, Competitiveness, Competitividad, Graphe complet, Complete graph, Grafo completo, Graphe distance, Distance graph, Grapho distancia, Informatique théorique, Computer theory, Informática teórica, Méthode optimisation, Optimization method, Método optimización, Optimalité asymptotique, Asymptotic optimality, Optimisation bicritères, Bicriteria optimization, Problème serveur, Online algorithms, Strong competitiveness
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Dipartimento di Informitica, University of L'Aquila, Via Veloio loc. Coppito, 67100 L'Aquila, Italy
Dipartimento di Informatica ed Automazione, University Roma Tre, Via delta Vasca Navale 79, 00146 Roma, Italy
ISSN:
0166-218X
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18159569
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics

Operational research. Management
Accession Number:
edscal.18159569
Database:
PASCAL Archive

Further Information

In 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.