article

A Graph-Theoretic Game and its Application to the $k$-Server Problem

Authors:

Noga Alon,

Richard M. Karp,

David Peleg,

Douglas WestAuthors Info & Claims

SIAM Journal on Computing, Volume 24, Issue 1

Pages 78 - 100

https://doi.org/10.1137/S0097539792224474

Published: 01 February 1995 Publication History

Abstract

This paper investigates a zero-sum game played on a weighted connected graph $G$ between two players, the tree player and the edge player . At each play, the tree player chooses a spanning tree $T$ and the edge player chooses an edge $e$. The payoff to the edge player is $cost(T,e)$, defined as follows: If $e$ lies in the tree $T$ then $cost(T,e)=0$; if $e$ does not lie in the tree then $cost(T,e) = cycle(T,e)/w(e)$, where $w(e)$ is the weight of edge $e$ and $cycle(T,e)$ is the weight of the unique cycle formed when edge $e$ is added to the tree $T$. The main result is that the value of the game on any $n$-vertex graph is bounded above by $\exp(O(\sqrt{\log n \log\log n}))$. It is conjectured that the value of the game is $O(\log n)$.

The game arises in connection with the $k$-server problem on a road network ; i.e., a metric space that can be represented as a multigraph $G$ in which each edge $e$ represents a road of length $w(e)$. It is shown that, if the value of the game on $G$ is $Val(G,w)$, then there is a randomized strategy that achieves a competitive ratio of $k(1 + Val(G,w))$ against any oblivious adversary. Thus, on any $n$-vertex road network, there is a randomized algorithm for the $k$-server problem that is $k\cdot\exp(O(\sqrt{\log n \log\log n}))$ competitive against oblivious adversaries.

At the heart of the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem . Specifically, for any $n$-vertex weighted, connected multigraph, the algorithm constructs a spanning tree $T$ such that the average, over all edges $e$, of $cost(T,e)$ is less than or equal to $\exp(O(\sqrt{\log n \log\log n}))$. This result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph.

Cited By

View all

Bustany IKahng AKoutis IPramanik BWang Z(2024)K-SpecPart: Supervised Embedding Algorithms and Cut Overlay for Improved Hypergraph PartitioningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333226843:4(1232-1245)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TCAD.2023.3332268
Teng S(2023)“Intelligent Heuristics Are the Future of Computing”ACM Transactions on Intelligent Systems and Technology10.1145/362770814:6(1-39)Online publication date: 14-Nov-2023
https://dl.acm.org/doi/10.1145/3627708
Chen LKyng RLiu YPeng RGutenberg MSachdeva S(2023)Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost FlowCommunications of the ACM10.1145/361094066:12(85-92)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3610940
Show More Cited By

Index Terms

A Graph-Theoretic Game and its Application to the $k$-Server Problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Tree spanners on chordal graphs: complexity and algorithms

A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The TREE t-SPANNER problem asks whether a graph admits a tree t-spanner, given t. We substantially ...
Computing almost shortest paths

We study the s-sources almost shortest paths (abbreviated s-ASP) problem. Given an unweighted graph G = (V,E), and a subset S &sube; V of s nodes, the goal is to compute almost shortest paths between ...
k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees

Low distortion probabilistic embedding of graphs into approximating trees is an extensively studied topic. Of particular interest is the case where the approximating trees are required to be (subgraph) spanning trees of the given graph (or multigraph), ...

Reviews

Reviewer: Yubao Guo

In connection with the k -server problem on a road network, consider a zero-sum game played on a weighted connected multigraph G (with the weight w e indicating the length of the edge e ) between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree T , and the edge player chooses an edge e . If e is not in T , then the cost is defined as cost T,e = e ??c w e ? /w e , where c is the unique cycle in T? e ; otherwise, cost T,e =0 . The authors prove that the value of the game on any n -vertex multigraph is less than or equal to exp O log n log log n , and conjecture that the value of the game is O log n .

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIAM Journal on Computing Volume 24, Issue 1

Feb. 1995

199 pages

ISSN:0097-5397

Editor:
Z. Galil
Columbia Univ., New York, NY; Tel-Aviv Univ., Tel-Aviv, Israel

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 February 1995

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

97
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bustany IKahng AKoutis IPramanik BWang Z(2024)K-SpecPart: Supervised Embedding Algorithms and Cut Overlay for Improved Hypergraph PartitioningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.333226843:4(1232-1245)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TCAD.2023.3332268
Teng S(2023)“Intelligent Heuristics Are the Future of Computing”ACM Transactions on Intelligent Systems and Technology10.1145/362770814:6(1-39)Online publication date: 14-Nov-2023
https://dl.acm.org/doi/10.1145/3627708
Chen LKyng RLiu YPeng RGutenberg MSachdeva S(2023)Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost FlowCommunications of the ACM10.1145/361094066:12(85-92)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3610940
Anagnostides ILenzen CHaeupler BZuzic GGouleakis T(2023)Almost universally optimal distributed Laplacian solvers via low-congestion shortcutsDistributed Computing10.1007/s00446-023-00454-036:4(475-499)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.1007/s00446-023-00454-0
Bustany IKahng AKoutis IPramanik BWang ZMitra TYoung EXiong J(2022)SpecPartProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design10.1145/3508352.3549390(1-9)Online publication date: 30-Oct-2022
https://dl.acm.org/doi/10.1145/3508352.3549390
Naves GShepherd FXia H(2022)Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximatorsMathematical Programming: Series A and B10.1007/s10107-022-01780-0197:2(1049-1067)Online publication date: 7-Mar-2022
https://dl.acm.org/doi/10.1007/s10107-022-01780-0
Gupta SKhodabakhsh AMortagy HNikolova E(2022)Electrical flows over spanning treesMathematical Programming: Series A and B10.1007/s10107-020-01614-x196:1-2(479-519)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10107-020-01614-x
Sengupta SPeri SAnjana P(2022)A Self-stabilizing Minimum Average Stretch Spanning Tree ConstructionNetworked Systems10.1007/978-3-031-17436-0_9(119-135)Online publication date: 17-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-17436-0_9
Goranci GRäcke HSaranurak TTan ZMarx D(2021)The expander hierarchy and its applications to dynamic graph algorithmsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458196(2212-2228)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458196
Forster SGoranci GHenzinger MMarx D(2021)Dynamic maintenance of low-stretch probabilistic tree embeddings with applicationsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458139(1226-1245)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458139
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Tree spanners on chordal graphs: complexity and algorithms

Computing almost shortest paths

k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations