Physical Sciences and Mathematics Commons^™

Approximation Algorithms For Problems In Makespan Minimization On Unrelated Parallel Machines, Daniel R. Page

Electronic Thesis and Dissertation Repository

A fundamental problem in scheduling is makespan minimization on unrelated parallel machines (R||C_max). Let there be a set J of jobs and a set M of parallel machines, where every job J_j ∈ J has processing time or length p_i,j ∈ ℚ⁺ on machine M_i ∈ M. The goal in R||C_max is to schedule the jobs non-preemptively on the machines so as to minimize the length of the schedule, the makespan. A ρ-approximation algorithm produces in polynomial time a feasible solution such that its objective value is within a multiplicative factor ρ of …

Local Search Approximation Algorithms For Clustering Problems, Nasim Samei

Electronic Thesis and Dissertation Repository

In this research we study the use of local search in the design of approximation algorithms for NP-hard optimization problems. For our study we have selected several well-known clustering problems: k-facility location problem, minimum mutliway cut problem, and constrained maximum k-cut problem.

We show that by careful use of the local optimality property of the solutions produced by local search algorithms it is possible to bound the ratio between solutions produced by local search approximation algorithms and optimum solutions. This ratio is known as the locality gap.

The locality gap of our algorithm for the k-uncapacitated facility …