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 15 of 15 for “"k-Server Problem"”.
-
Restricted k-server problem
Thesis (M.S.)--Michigan State University. Department of Computer Science and Engineering, 2004
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
Uma abordagem utilizando aprendizagem por reforço hierárquica e computação paralela para o problema dos K-Servos
… model for a class of online optimization problems, including paging, access lists, industry oil problems such as the management of workover rigs and logistics in the production of offshore oil, the problem of K-Servos, among others. The use of reinforcement learning to solving these …
-
Overcoming Computational Complexity Barriers for Optimal Transport in Discrete and Semi-Discrete Settings
… semi-discrete (resp. discrete) optimal transport problem asks for computing a minimum-cost plan to transport mass between $mu$ and $nu$. In the special case of the discrete OT problem, where $mu$ and $nu$ are defined on sets $A$ and $B$ of $n$ points each, and any point in $Acup B$ is given $1/n$ …
-
Combinatorial Algorithms for Server Allocation Problem
Motivated by problems in logistics, image 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 …
-
Algorithms for Networks With Uncertainty
<p>In this dissertation, we study algorithmic problems motivated by the optimization of networks under uncertainty.</p><p>We summarize our contributions:</p><p>\begin{itemize}</p><p>\item \textbf{Subset $k$-server:} We propose and give algorithms for the \emph{all-or-one $k$-server}, a …
-
Serving online requests with mobile resources
Resource allocation problems have a large variety of applications in different areas of computer science and operations research. A resource allocation problem seeks to find an optimal allocation of a given type of expensive or limited resource to a set of clients that request the services of the …
-
Various Approaches to the Stochastic K-Server and Stacker-Crane Problems
… down. In this thesis we present these types of problems in a more general framework, expanding applicability of our discussion to an even wider domain of problems. We present fast new al- gorithms with supporting theoretical and experimental analysis, providing certain guarantees about how close …
-
Separation and Cover Problems in Temporal Graph
… of the Vertex Separator and Vertex Cover problems from the static world with an emphasis on the Vertex Separator problem. An (s,z)-temporal separator is a set of vertices whose removal disconnects vertex s from vertex z for every time step in a temporal graph. The (s,z)-Temporal Separator …