H. Gökalp Demirci

H. Gökalp Demirci

PhD student

Computer Science Department

University of Chicago

Research
Experience

Optimization and approximation algorithms for combinatorial problems:

• Scheduling problems with applications in High Performance Computing (HPC)

⁃ STACS’18 improved bounds on scheduling under precedence and power constraints by an exponential factor using novel linear programming relaxations

⁃ SuperComputing’18 extended these bounds to configurable HPC setting and demonstrated better performance than state-of-the-art schedulers: [github.com/PowerCapDAG]

• Clustering problems such as k-means, k-median, and facility location

⁃ ICALP’16 improved capacity violation factor of k-median problem significantly by solving an exponentially large LP relaxation using a tricky separation oracle for the ellipsoid method

Internship Experience

Software Engineer Intern at Google

Jan - Mar 2019

Ongoing internship.

Software Engineer Intern at ICY Capital

Jun - Sep 2016

Designed and implemented a more efficient algorithm for a key component of a new trading strategy. Did hyperparameter search for the new strategy and backtested it.

Education

University of Chicago

MS in Computer Science, 2016

Thesis: Constant Approximation for Capacitated k-Median with (1 + \epsilon)-Capacity Violation

Boğaziçi University

BS, MS in Computer Engineering, 2013

Thesis: The Complexity of Debate Checking, Advisor: Cem Say

Publications

A Divide and Conquer Algorithm for DAG Scheduling under Power Constraints

SuperComputing 2018

G. Demirci, I. Marincic, H. Hoffmann

We design an algorithm for scheduling precedence DAGs under a power-cap with an unusual paradigm: divide-and-conquer. We prove an O(log n)-approximate guarantee on its performance. We implement our algorithm and a simulation environment around power/performance data collected from real HPC applications. Comparison against several state-of-the-art "greedy" schedulers show that our algorithm performs much better especially under severe power restrictions.

Github! Check out the simulation environment and the various scheduling algorithms! Ask me for a more up-to-date version!

Approximation Algorithms for Scheduling with Resource and Precedence Constraints

STACS 2018

G. Demirci, H. Hoffmann, D. Kim

We design the first algorithms with nontrivial approximation ratios for simultaneously precedence and resource constrained scheduling. Our algorithms use a divide-and-conquer approach for the minimum makespan objective. Then we make extensive use of new linear programming relaxations for generalization to weighted completion time objective and machines running at different speeds.

Constant Approximation for Capacitated k-Median with (1 + \epsilon)-Capacity Violation

ICALP 2016

G. Demirci, S. Li

Capacitated k-median is a variation of the classical clustering problem with capacities specified for cluster sizes. Our work brings down the capacity violation factor from 3 to (1 + \epsilon) for a constant approximation-factor. We use an exponential size linear programming relaxation for the problem. Instead of solving the LP directly, we combine our rounding algorithm with the ellipsoid method in a "round-or-separate" fashion to solve the large LP efficiently.

The Complexity of Debate Checking

Theory of Computing Systems 2015

G. Demirci, C. Say, A. Yakaryılmaz

Debates with small transparent quantum verifiers

DLT 2014, Invited to the special issue in International Journal of Foundations of Computer Science

A. Yakaryılmaz, C. Say, G. Demirci

Classical and quantum realtime alternating automata

NCMA 2014

G. Demirci, M. Hirvensalo, K. Reinhardt, C. Say, A. Yakaryılmaz