Seminars: K. S. Kobylkin, Complexity and inapproximability for problems of finding minimum set of stabbing objects on geometric graphs

SEMINARS


Seminar for Optimization Laboratory November 13, 2015 11:30, Ekaterinburg, Sofyi Kovalevskoi st., 16

Complexity and inapproximability for problems of finding minimum set of stabbing objects on geometric graphs K. S. Kobylkin^ab ^a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg ^b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg
Abstract: We consider a problem of seeking minimum set of stabbing objects for straight line segments which are edges of geometric graph $G.$ In our talk we give some complexity and inapproximability results (integrality gap lower bounds) for these problems considered both in the case of an arbitrary and planar graph $G$ where class of stabbers is restricted to disks of fixed positive radius and to straight lines of an arbitrary orientation.