Algorithms for Locating Facilities under Uncertainties

Other Titles


One of the main challenges in the area of discrete optimization is to find efficient and effective ways of solving problems that arise in day-to-day life. Traditionally, algorithms for such problems require complete knowledge of input parameters which is often undesirable and unrealistic. In this dissertation we consider some well-known hard location problems when the input parameters are not completely known in advance and design efficient algorithms for such scenarios guaranteeing quality of output solutions.

In the first part of the dissertation we give a general framework and algorithmic approach for incremental approximation algorithms. Given a notion of ordering on solutions of different cardinalities, we give solutions for all cardinalities such that the solutions respect the ordering and our solution is close in value to the value of an optimal solution of cardinality k for all values of k. We apply our framework to the incremental version of the k-median problem, k-MST problem, k-vertex cover problem, k-set cover problem and the facility location problem and give new or improved incremental algorithms for these problems. We also show that our framework applies to hierarchical clustering problems.

In the second part we consider the problem of leasing facilities over time where a newly arriving demand has to be either assigned to a previously leased open facility or to a newly leased facility. The serving cost of a demand can be defined as its distance from its assigned facility. The goal of the problem is to buy a set of leases at different facilities that minimizes the sum of leasing and serving costs. We give the first constant factor approximation algorithm for the offline version of the problem achieving a factor of 3. We also give the first deterministic algorithm for the online version that is O(K log n)-competitive where K is the number of available facility leases and n is the number of clients.

We also compare the running times and quality of the solutions given by our incremental and hierarchical k-median algorithms with existing algorithms on different k-median datasets and verify that the quality of our solutions are better than the solutions of existing algorithms.

Journal / Series

Volume & Issue



Date Issued




Algorithms; Approximation; Optimization; Location Problems


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record