[Colloquium] Demirci/Dissertation Defense/Apr 22, 2019

[Margaret Jaffey]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Gokalp Demirci

Date:  Monday, April 22, 2019

Time:  9:30 AM

Place:  John Crerar Library (JCL) 390

Title: APPROXIMATION ALGORITHMS FOR CAPACITATED K-MEDIAN AND
SCHEDULING WITH RESOURCE AND PRECEDENCE CONSTRAINTS

Abstract:
This thesis proposes approximation algorithms for two combinatorial
optimization problems: 1) Capacitated k-Median, and 2) Scheduling with
Resource and Precedence Constraints.

In the first problem, we are given a set of clients and a set of
facilities in a metric space such that a set of k facilities need to
be open and each client needs to be assigned to an open facility
(clustered around) to minimize the sum of client-facility distances.
In addition, we have capacity constraints associated with each
facility in the input to indicate the maximum number of clients that
can be assigned to that facility. We give a constant-factor
approximation algorithm for this problem by rounding a linear
programming relaxation. In line with the previous approximation
algorithms for the same problem, this is a pseudo-approximation
algorithm that violates the capacities by at most a factor of (1 +
epsilon).

In the second problem, we have a set of jobs to be scheduled on a set
of machines to minimize either the makespan of the schedule or the
more general total weighted completion time. Jobs have precedence
constraints between them. Each job also have a resource requirement
and the total resource use of jobs running concurrently at any point
in a feasible schedule should not exceed the global resource cap given
in the input. We initially use a divide-andconquer approach to obtain
a O(log n)-approximation for the minimum makespan objective on
identical machines. Then, we generalize the result to weighted
completion time objective and uniformly related machines by combining
the initial divide-and-conquer method with linear programming
relaxations for these variations. Furthermore, we adapt our algorithm
as a solution to an emerging problem in High Performance Computing
(HPC): scheduling precedence constrained jobs under a power cap. We
implement our algorithm and compare it to state-of-the-art greedy
methods in a simulation environment on a variety of precedence
relationships and power/performance data collected from real HPC
applications. We find that our divide-and-conquer method improves
performance by up to 75% compared to greedy scheduling algorithms.

Gokalp's advisors are Prof. Janos Simon and Prof. Hank Hoffmann

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://newtraell.cs.uchicago.edu/phd/phd_announcements#demirci

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=