# 6th Colloquium of Research Area KL

Date: April 29, 2016

Venue:  Seminar room 1st floor, Arithmeum, Lennéstr. 2, Bonn

## Program:

 15:45 Coffee and Tee (Lounge 2nd floor, Arithmeum, Lennéstr. 2) 16:15 Jochen Könemann: Technology Diffusion: From Precedence-Constrained Deadline Scheduling to Information Cascades in Networks 17:00 Coffee break 17:30 Melanie Schmidt: Local k-median and k-means clustering After the Colloquium there will be the opportunity to have dinner together

## Abstracts:

#### Jochen Könemann: Technology Diffusion: From Precedence-Constrained Deadline Scheduling to Information Cascades in Networks

We consider the classic problem of scheduling n jobs non-preemptively on a single machine. Each job $j$ has nonnegative processing time, weight, and deadline, and a feasible schedule needs to be consistent with chain-like precedence constraints. The goal is to compute a feasible schedule that minimizes the sum of penalties of late jobs. Lenstra and Rinnooy Kan [Annals of Disc. Math., 1977] in their seminal work introduced this problem and showed that it is strongly NP-hard, even when all processing times and weights are 1. We study the approximability of the problem and our main result is an $O(\log k)$-approximation algorithm for instances with $k$ distinct job deadlines.

We also point out a surprising connection to a model for technology diffusion processes in networks that was recently proposed by Goldberg and Liu [SODA, 2013]. Specifically, we will show that the so called "target-set selection" problem in this model is (in some cases) equivalent to the above deadline scheduling problem.

Joint work with H. Efsandiari, M. Hajiaghayi, H. Mahini, D. Malec & L. Sanità

Top

#### Melanie Schmidt: Local k-median and k-means clustering

Partitional clustering divides a set of input points into $k$ subsets and usually represents each subset by a center. Two popular examples are the $k$-median and the $k$-means problem which minimize the sum of the (squared) distances of each point to the center of its subset.

Due to better adaptability to applications, recent research turns to study clustering with additional constraints like capacitated clustering, clustering with lower bounds, with outliers or with balance constraints. This talk is about an extension that we name local $k$-median/$k$-means. Here, every potential center has a radius and points can only be represented by the center if they lie within the radius.

Local $k$-median can be used to solve the aversion $k$-clustering problem which emerges in the study of extensiveform games. We develop a bicriteria approximation for local $k$-median that induces a constant factor approximation for the aversion $k$-clustering problem. The talk is based on joint work with Anupam Gupta and Guru Guruganesh.

Top