Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 21 for “"k-server"”.
-
Restricted k-server problem
Thesis (M.S.)--Michigan State University. Department of Computer Science and Engineering, 2004
-
The Incremental Constraint of k-Server
… lower bound of the incremental constraint of k-server is shown to be to 2.
-
On-Line Algorithms and the k-Server Conjecture
… Algorithm, a natural algorithm for the ^-server problem, is shown to have competitive ratio at most 2k —1 for all metric spaces. It is also shown that the ^-server conjecture, which states that there is an on-line algorithm for the /^-server problem with competitive ratio k, holds for all …
-
Competitive analysis of k-server variants and metrical task systems
<p>In the online k-server problem, an algorithm controls k mobile servers in a metric space. One by one, requests arrive at points of the space, and the algorithm must serve each request by selecting a server to visit it. The goal is to minimize the total distance traveled by all servers. In the …
-
Various Approaches to the Stochastic K-Server and Stacker-Crane Problems
In recent years there has been a trend towards large-scale logistics for individual members of the public, such as ride-sharing services and drone package delivery. Efficient coordination of pickups and deliveries is essential in order to keep costs and wait times down. In this thesis we present …
-
Empirical Analysis of Algorithms for the k-Server and Online Bipartite Matching Problems
The k–server problem is of significant importance to the theoretical computer science and the operations research community. In this problem, we are given k servers, their initial locations and a sequence of n requests that arrive one at a time. All these locations are points from some metric space …
-
T-theory and analysis of online algorithms
… of several online algorithms for the k-server problem, although the standard notation of T-theory was not used at the time of their creation; A summary of the k-server problem, and some important concepts of T-theory, are given. A number of known k-server results are restated using the …
-
Algorithms for Networks With Uncertainty
… \textbf{Subset $k$-server:} We propose and give algorithms for the \emph{all-or-one $k$-server}, a generalization of classical $k$-server problem.</p><p> $k$-server is an example of a problem in an \emph{online setting}: the algorithm must make irrevocable decisions …
-
Alternative settings and models of the certain news network problem
The classic k-server problem has been studied extensively in the context of competitive analysis for online problems. In this problem, a set of k servers move on a metric space to serve requests that appear in an online fashion on the nodes of the space. The goal is to move servers in a way to …
-
Aprendizagem por reforço profundo uma nova perspectiva sobre o problema dos k-servos
The k-server problem in a weighted graph (or metric space) is defined by the need to efficiently move k servers to fulfill a sequence of requests that arise online at each graph node. This is perhaps the most influential online computation problem whose solution remains open, serving as an …
-
The randomized server problem
In the k-server problem there are k ≥ 2 identical servers which are located at k points in a metric space M. If there is a request to a point r ∈ M, one of the servers must be moved to the request point in order to "serve" this request. The cost of this service is the distance between the points …
-
Overcoming Computational Complexity Barriers for Optimal Transport in Discrete and Semi-Discrete Settings
… to the offline version of the classical $k$-server problem reduces to solving a minimum-cost partial bipartite matching between two point sets $A$ and $B$ within that metric space. Our final result in this thesis is the following: 5. Efficient exact offline algorithm for $k$-server: We …
-
Online Network Design under Uncertainty
… survivable network design, and stochastic k-server. We analyze their complexity and design competitive algorithms for them.
-
Uma abordagem utilizando aprendizagem por reforço hierárquica e computação paralela para o problema dos K-Servos
… proportional to the number n of nodes and k of servers, it is noticed that their growth is given exponentially (𝐶𝑘𝑛≅𝑂(𝑛𝑘)). To circumvent this, the problem was modeled with a multi-step decision process where we initially used the k-means algorithm as a grouping method to decompose the problem …
-
Supporting Distributed Transaction Processing Over Mobile and Heterogeneous Platforms
… P2P overlay networks and a generalized Top-K server selection algorithm for load balancing, which could be optimized based on multiple factors such as proximity and cost. The proposed push-pull hybrid interfaces greatly reduce the overhead of directory servers caused by frequent queries from …
-
Serving online requests with mobile resources
… of the OMFL problem that is closer to the k-server problem, arguably one of the most influential problem in the area of online algorithms and competitive analysis.
-
Combinatorial Algorithms for Server Allocation Problem
… recognition, and statistics, we consider the server allocation problem. In this problem, we are given $k$ servers (with capacities) and $n$ requests, which are points in a metric space. A server serves a request by moving to the request location, and the goal is to serve all requests while …
-
Separation and Cover Problems in Temporal Graph
… the famous Double Coverage algorithm for the k-Server problem on a line in the area of online algorithms. This highlights an interesting cross-over between temporal graph algorithms and online algorithms that might require further investigation. Lastly, we present a polynomial-time algorithm for …
Page 1 of 2