Empirical Analysis of Algorithms for the k-Server and Online Bipartite Matching Problems
| dc.contributor.author | Mahajan, Rutvij Sanjay | en |
| dc.contributor.committeechair | Vullikanti, Anil Kumar S. | en |
| dc.contributor.committeemember | Raghvendra, Sharath | en |
| dc.contributor.committeemember | Tokekar, Pratap | en |
| dc.contributor.department | Electrical and Computer Engineering | en |
| dc.date.accessioned | 2020-02-06T07:00:36Z | en |
| dc.date.available | 2020-02-06T07:00:36Z | en |
| dc.date.issued | 2018-08-14 | en |
| dc.description.abstract | 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 and the cost of serving a request is given by the distance between the location of the request and the current location of the server selected to process the request. We must immediately process the request by moving a server to the request location. The objective in this problem is to minimize the total distance traveled by the servers to process all the requests. In this thesis, we present an empirical analysis of a new online algorithm for k-server problem. This algorithm maintains two solutions, online solution, and an approximately optimal offline solution. When a request arrives we update the offline solution and use this update to inform the online assignment. This algorithm is motivated by the Robust-Matching Algorithm [RMAlgorithm, Raghvendra, APPROX 2016] for the closely related online bipartite matching problem. We then give a comprehensive experimental analysis of this algorithm and also provide a graphical user interface which can be used to visualize execution instances of the algorithm. We also consider these problems under stochastic setting and implement a lookahead strategy on top of the new online algorithm. | en |
| dc.description.abstractgeneral | Motivated by real-time logistics, we study the online versions of the well-known bipartite matching and the k-server problems. In this problem, there are servers (delivery vehicles) located in different parts of the city. When a request for delivery is made, we have to immediately assign a delivery vehicle to this request without any knowledge of the future. Making cost-effective assignments, therefore, becomes incredibly challenging. In this thesis, we implement and empirically evaluate a new algorithm for the k-server and online matching problems. | en |
| dc.description.degree | MS | en |
| dc.format.medium | ETD | en |
| dc.identifier.other | vt_gsexam:16763 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/96725 | en |
| dc.publisher | Virginia Tech | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject | k-Server Problem | en |
| dc.subject | Work Function Algorithm | en |
| dc.subject | Bipartite Matching | en |
| dc.subject | Assignment Problem | en |
| dc.title | Empirical Analysis of Algorithms for the k-Server and Online Bipartite Matching Problems | en |
| dc.type | Thesis | en |
| thesis.degree.discipline | Computer Engineering | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | masters | en |
| thesis.degree.name | MS | en |