Search
Skip to Search Results- 1Approximation Algorithm
- 1Approximation Algorithms
- 1Approximation algorithms
- 1Column Generation
- 1Combinatorial Optimization
- 1DCVR
-
Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
DownloadFall 2022
In this study, we present an improved approximation algorithm for three related problems. In the Minimum Sum of Radii clustering problem (MSR), we aim to select k balls in a metric space to cover all points while minimizing the sum of the radii. In the Minimum Sum of Diameters clustering problem...
-
Solving the LP Relaxation of Distance-Constrained Vehicle Routing Problem Using Column Generation
DownloadFall 2020
The distance-constrained vehicle routing problem (DVRP) is one of the less studied variants of vehicle routing problems. Here, the objective is to deliver packages from a depot to clients with as few delivery vehicles as possible within a given time frame. In this thesis, we tackle larger...
-
Spring 2017
Budgeted Red-Blue Median is a generalization of classic k-Median in that there are two sets of facilities, say R and B, that can be used to serve clients located in some metric space. The goal is to open kr facilities in R and kb facilities in B for some given bounds kr,kb and connect each client...