Discrete Applied Math Seminar By Iyad Kanj: Covering Segments with Unit Intervals

Speaker:

Iyad Kanj, DePaul University

Title:

Covering Segments with Unit Intervals

Abstract:

In this talk, we will discuss the problem of covering a set of segments on a line with the minimum number of unit-length intervals.  This problem generalizes a classical (textbook) problem and has applications in network security and storage systems.

We will show that the case where all the segments have the same length is NP-hard, extending and strengthening several results in the literature. 

We will then discuss the parameterized complexity of the problem and show that it is fixed-parameter tractable in the case where all the segments have the same length and is parameterized intractable otherwise.

Bio:

Iyad Kanj is a Professor of Computer Science in the School of Computing at DePaul University. He joined DePaul University in 2001, after completing his Ph.D. degree at Texas A&M University.

His research interests include parameterized algorithms, graph algorithms, and computational geometry. His recent work focuses on applications of the aforementioned areas to AI and robot path planning. 

 

The Discrete Applied Math seminar will be held most Fridays from 3:30 p.m. - 4:30 p.m. on Zoom during the Spring 2022 semester.

 

Discrete Applied Math seminar