arXiv preprint ·
On the Offline Version of the Time-Optimal k-Server Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We consider the offline problem of parallel relocation of k identical mobile resources. After each request, known in advance, the resources may move simultaneously, and the duration of a step is determined by the longest individual movement. This model is equivalent to the offline version of the time-optimal k-server problem. We prove that the decision version is strongly NP-complete already on metrics of finite subsets of the Euclidean line, or equivalently, on vertex metrics of weighted paths. Thus, the computational hardness persists even under a linear arrangement of the admissible resource locations. As a positive result, we show that the problem can be solved exactly in polynomial time on metrics of undirected unweighted graphs with a universal vertex.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable
Factorisability of Low Dimensional Non-Negative Integer Matrices
FPT Isomorphism Test for $F$-Free Tournaments
Backtracking Candidate Elimination: A One-Pass Algorithm for the Chip Testing Problem
Minimum Sum Vertex Cover via Minimum Vertex Cover
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.