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 4 of 4 for “"Linear-programming rounding"”.
-
Approximation Algorithms for Resource Allocation
… several new techniques, predominantly, a new linear programming rounding methodology and a constructive aspect of a well-known probabilistic method, the Lov\'{a}sz Local Lemma (LLL). Second, we employ these techniques to applications of resource allocation obtaining substantial improvements …
-
A heuristic approach to supply chain network design in a multi-commodity four-echelon logistics system
… initially modeled as a large-scale Mixed Integer Linear Program (MILP). In the construction phase, a linear programming rounding strategy is applied to obtain initial values for the integer location variables in the model. Simultaneously, a Multi-start method was developed to generate diversified …
-
Randomized Kernel Rounding for Routing, Scheduling, and Machine Learning
… intermediate solutions due to convex/linear relaxations of the problems, using kernels that can be adapted for best performance, can significantly improve approximation guarantees for multiple such problems. The first set of problems that we study, in Chapter 2, are routing problems …
-
Approximation Algorithms for Clustering and Facility Location Problems
… algorithm due to [34] based on LP-rounding. Our results extend to the weighted generalization wherein each facility i has a non-negative weight w_i and the movement cost for i is w_i times the distance traveled by i. In Chapter 3, we consider a facility-location problem that we call …