{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/86518"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/86518","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Input Sensitive Analysis of a Minimum Metric Bipartite Matching Algorithm","abstract":"In various business and military settings, there is an expectation of on-demand delivery of supplies and services. Typically, several delivery vehicles (also called servers) carry these supplies. Requests arrive one at a time and when a request arrives, a server is assigned to this request at a cost that is proportional to the distance between the server and the request. Bad assignments will not only lead to larger costs but will also create bottlenecks by increasing delivery time. There is, therefore, a need to design decision-making algorithms that produce cost-effective assignments of servers to requests in real-time. In this thesis, we consider the online bipartite matching problem where each server can serve exactly one request. In the online minimum metric bipartite matching problem, we are provided with a set of server locations in a metric space. Requests arrive one at a time that have to be immediately and irrevocably matched to a free server. The total cost of matching all the requests to servers, also known as the online matching is the sum of the cost of all the edges in the matching. There are many well-studied models for request generation. We study the problem in the adversarial model where an adversary who knows the decisions made by the algorithm generates a request sequence to maximize ratio of the cost of the online matching and the minimum-cost matching (also called the competitive ratio). An algorithm is a-competitive if the cost of online matching is at most 'a' times the minimum cost. A recently discovered robust and deterministic online algorithm (we refer to this as the robust matching or the RM-Algorithm) was shown to have optimal competitive ratios in the adversarial model and a relatively weaker random arrival model. We extend the analysis of the RM-Algorithm in the adversarial model and show that the competitive ratio of the algorithm is sensitive to the input, i.e., for \"nice\" input metric spaces or \"nice\" server placements, the performance guarantees of the RM-Algorithm is significantly better. In fact, we show that the performance is almost optimal for any fixed metric space and server locations.","abstract_html":"In various business and military settings, there is an expectation of on-demand delivery of supplies and services. Typically, several delivery vehicles (also called servers) carry these supplies. Requests arrive one at a time and when a request arrives, a server is assigned to this request at a cost that is proportional to the distance between the server and the request. Bad assignments will not only lead to larger costs but will also create bottlenecks by increasing delivery time. There is, therefore, a need to design decision-making algorithms that produce cost-effective assignments of servers to requests in real-time. In this thesis, we consider the online bipartite matching problem where each server can serve exactly one request. In the online minimum metric bipartite matching problem, we are provided with a set of server locations in a metric space. Requests arrive one at a time that have to be immediately and irrevocably matched to a free server. The total cost of matching all the requests to servers, also known as the online matching is the sum of the cost of all the edges in the matching. There are many well-studied models for request generation. We study the problem in the adversarial model where an adversary who knows the decisions made by the algorithm generates a request sequence to maximize ratio of the cost of the online matching and the minimum-cost matching (also called the competitive ratio). An algorithm is a-competitive if the cost of online matching is at most 'a' times the minimum cost. A recently discovered robust and deterministic online algorithm (we refer to this as the robust matching or the RM-Algorithm) was shown to have optimal competitive ratios in the adversarial model and a relatively weaker random arrival model. We extend the analysis of the RM-Algorithm in the adversarial model and show that the competitive ratio of the algorithm is sensitive to the input, i.e., for "nice" input metric spaces or "nice" server placements, the performance guarantees of the RM-Algorithm is significantly better. In fact, we show that the performance is almost optimal for any fixed metric space and server locations.","abstract_has_math":false,"creators":["Nayyar, Krati"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Computer Science and Applications","degree_department":"Computer Science","school":null,"contributors":[],"advisors":[],"committee_chairs":["Raghvendra, Sharath"],"committee_members":["Heath, Lenwood S.","Murali, T. M."],"year":2017,"date_issued":"2017-06-29","date_published":"2017-06-29","updated_at":"2026-07-22T22:20:27Z","subjects":["online algorithms","weighted matching","competitive ratio","input sensitive"],"languages":[],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:11014"],"render_values":[{"text":"vt_gsexam:11014","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/86518","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Raghvendra, Sharath"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Heath, Lenwood S.","Murali, T. M."]},{"key":"dc:contributor.department","label":"Department","values":["Computer Science"]},{"key":"dc:creator","label":"Author","values":["Nayyar, Krati"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2018-12-22T07:00:29Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-12-22T07:00:29Z"]},{"key":"dc:date.issued","label":"Date","values":["2017-06-29"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Applications"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["online algorithms","weighted matching","competitive ratio","input sensitive"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:11014"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/86518"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In various business and military settings, there is an expectation of on-demand delivery of supplies and services. Typically, several delivery vehicles (also called servers) carry these supplies. Requests arrive one at a time and when a request arrives, a server is assigned to this request at a cost that is proportional to the distance between the server and the request. Bad assignments will not only lead to larger costs but will also create bottlenecks by increasing delivery time. There is, therefore, a need to design decision-making algorithms that produce cost-effective assignments of servers to requests in real-time. In this thesis, we consider the online bipartite matching problem where each server can serve exactly one request. In the online minimum metric bipartite matching problem, we are provided with a set of server locations in a metric space. Requests arrive one at a time that have to be immediately and irrevocably matched to a free server. The total cost of matching all the requests to servers, also known as the online matching is the sum of the cost of all the edges in the matching. There are many well-studied models for request generation. We study the problem in the adversarial model where an adversary who knows the decisions made by the algorithm generates a request sequence to maximize ratio of the cost of the online matching and the minimum-cost matching (also called the competitive ratio). An algorithm is a-competitive if the cost of online matching is at most 'a' times the minimum cost. A recently discovered robust and deterministic online algorithm (we refer to this as the robust matching or the RM-Algorithm) was shown to have optimal competitive ratios in the adversarial model and a relatively weaker random arrival model. We extend the analysis of the RM-Algorithm in the adversarial model and show that the competitive ratio of the algorithm is sensitive to the input, i.e., for \"nice\" input metric spaces or \"nice\" server placements, the performance guarantees of the RM-Algorithm is significantly better. In fact, we show that the performance is almost optimal for any fixed metric space and server locations."]},{"key":"dc:description.abstractgeneral","label":"General Abstract","values":["In various business and military settings, there is an expectation of on-demand delivery of supplies and services. Typically, several delivery vehicles (also called servers) carry these supplies. Requests arrive one at a time and when a request arrives, a server is assigned to this request at a cost that is proportional to the distance between the server and the request. Bad assignments will not only lead to larger costs but will also create bottlenecks by increasing delivery time. There is, therefore, a need to design decision-making algorithms that produce cost-effective assignments of servers to requests in real-time. In this thesis, we consider the online bipartite matching problem where each server can serve exactly one request. In the online minimum metric bipartite matching problem, we are provided with a set of server locations in a metric space. Requests arrive one at a time that have to be immediately and irrevocably matched to a free server. The total cost of matching all the requests to servers, also known as the online matching is the sum of the cost of all the edges in the matching. There are many well-studied models for request generation. We study the problem in the adversarial model where an adversary who knows the decisions made by the algorithm generates a request sequence to maximize ratio of the cost of the online matching and the minimum-cost matching (also called the competitive ratio). An algorithm is α-competitive if the cost of online matching is at most α times the minimum cost. A recently discovered robust and deterministic online algorithm (we refer to this as the robust matching or the RM-Algorithm) was shown to have optimal competitive ratios in the adversarial model and a relatively weaker random arrival model. We extend the analysis of the RM-Algorithm in the adversarial model and show that the competitive ratio of the algorithm is sensitive to the input, i.e., for “nice” input metric spaces or “nice” server placements, the performance guarantees of the RM-Algorithm is significantly better. In fact, we show that the performance is almost optimal for any fixed metric space and server locations."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["ETD"]},{"key":"dc:title","label":"Title","values":["Input Sensitive Analysis of a Minimum Metric Bipartite Matching Algorithm"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Raghvendra, Sharath"],"dc:contributor.committeemember":["Heath, Lenwood S.","Murali, T. M."],"dc:contributor.department":["Computer Science"],"dc:creator":["Nayyar, Krati"],"dc:date.accessioned":["2018-12-22T07:00:29Z"],"dc:date.available":["2018-12-22T07:00:29Z"],"dc:date.issued":["2017-06-29"],"dc:description.abstract":["In various business and military settings, there is an expectation of on-demand delivery of supplies and services. Typically, several delivery vehicles (also called servers) carry these supplies. Requests arrive one at a time and when a request arrives, a server is assigned to this request at a cost that is proportional to the distance between the server and the request. Bad assignments will not only lead to larger costs but will also create bottlenecks by increasing delivery time. There is, therefore, a need to design decision-making algorithms that produce cost-effective assignments of servers to requests in real-time. In this thesis, we consider the online bipartite matching problem where each server can serve exactly one request. In the online minimum metric bipartite matching problem, we are provided with a set of server locations in a metric space. Requests arrive one at a time that have to be immediately and irrevocably matched to a free server. The total cost of matching all the requests to servers, also known as the online matching is the sum of the cost of all the edges in the matching. There are many well-studied models for request generation. We study the problem in the adversarial model where an adversary who knows the decisions made by the algorithm generates a request sequence to maximize ratio of the cost of the online matching and the minimum-cost matching (also called the competitive ratio). An algorithm is a-competitive if the cost of online matching is at most 'a' times the minimum cost. A recently discovered robust and deterministic online algorithm (we refer to this as the robust matching or the RM-Algorithm) was shown to have optimal competitive ratios in the adversarial model and a relatively weaker random arrival model. We extend the analysis of the RM-Algorithm in the adversarial model and show that the competitive ratio of the algorithm is sensitive to the input, i.e., for \"nice\" input metric spaces or \"nice\" server placements, the performance guarantees of the RM-Algorithm is significantly better. In fact, we show that the performance is almost optimal for any fixed metric space and server locations."],"dc:description.abstractgeneral":["In various business and military settings, there is an expectation of on-demand delivery of supplies and services. Typically, several delivery vehicles (also called servers) carry these supplies. Requests arrive one at a time and when a request arrives, a server is assigned to this request at a cost that is proportional to the distance between the server and the request. Bad assignments will not only lead to larger costs but will also create bottlenecks by increasing delivery time. There is, therefore, a need to design decision-making algorithms that produce cost-effective assignments of servers to requests in real-time. In this thesis, we consider the online bipartite matching problem where each server can serve exactly one request. In the online minimum metric bipartite matching problem, we are provided with a set of server locations in a metric space. Requests arrive one at a time that have to be immediately and irrevocably matched to a free server. The total cost of matching all the requests to servers, also known as the online matching is the sum of the cost of all the edges in the matching. There are many well-studied models for request generation. We study the problem in the adversarial model where an adversary who knows the decisions made by the algorithm generates a request sequence to maximize ratio of the cost of the online matching and the minimum-cost matching (also called the competitive ratio). An algorithm is α-competitive if the cost of online matching is at most α times the minimum cost. A recently discovered robust and deterministic online algorithm (we refer to this as the robust matching or the RM-Algorithm) was shown to have optimal competitive ratios in the adversarial model and a relatively weaker random arrival model. We extend the analysis of the RM-Algorithm in the adversarial model and show that the competitive ratio of the algorithm is sensitive to the input, i.e., for “nice” input metric spaces or “nice” server placements, the performance guarantees of the RM-Algorithm is significantly better. In fact, we show that the performance is almost optimal for any fixed metric space and server locations."],"dc:description.degree":["Master of Science"],"dc:format.medium":["ETD"],"dc:identifier.other":["vt_gsexam:11014"],"dc:identifier.uri":["http://hdl.handle.net/10919/86518"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["online algorithms","weighted matching","competitive ratio","input sensitive"],"dc:title":["Input Sensitive Analysis of a Minimum Metric Bipartite Matching Algorithm"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer Science and Applications"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:20:27Z"}