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 7 of 7 for “"K-Server Problem"”.
-
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 …
-
A robust optimization approach to online problems
In this thesis, we consider online optimization problems that are characterized by incrementally revealed input data and sequential irrevocable decisions that must be made without complete knowledge of the future. We employ a combination of mixed integer optimization (MIO) and robust optimization …
-
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
… 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 …
-
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 …