Geometric Optimization 202-2-6281
Fall 2019

Prerequisite: Algorithms

Some background in Computational Geometry is needed in order to understand some of the material. Most of this background will be provided in class when it becomes relevant; in some cases though the students will be referred to specific pages in one of the Computational Geometry textbooks.

Announcements:

Instructor:

Matya Katz  ( matya@cs.bgu.ac.il ) 

Office hours: Wednesday 14:15-16:00, Alon building (37), room 212, Tel: (08) 6461628

 

Teaching Assistant:

          Elad Sulami

 

Class Time:

Monday 14-16 (building 97, room 202)

Course Description:

The course deals with various topics in geometric optimization. Several techniques and a selection of approximation algorithms will be presented. More precisely, a subset of the following optimization techniques will be discussed: parametric searching and searching in sorted matrices, the shifting strategy, geometric local search, epsilon-nets and epsilon-approximations, core sets, (geometric) linear programming. In addition, approximation algorithms (mostly based on these techniques) dealing with, e.g., geometric covering, (wireless) network design, and facility location will be presented. 

Bibliography:

Most of the material is taken from recent papers and cannot be found in textbooks.There are several survey papers on geometric optimization and on specific topics in geometric optimization. References will be provided later on.

A recommended textbook in computational geometry is

M. de Berg,  Otfried Cheong, Marc van Kreveld, Mark Overmars

Springer-Verlag

Requirements, Assignments and Grades:

Attendance: You may miss up to 6 classes. This is a necessary condition for passing the course.

The final grade will be determined by 4 homework assignments (~50%), and a final project which may include (among other requirements) the presentation of a scientific paper (~50%).

 

Assignment No. 1 – due November 18, 2019

Assignment No. 2 – due December 4, 2019

Assignment No. 3 – due December 23, 2019

Assignment No. 4 – due January 20, 2020

 

 

 

Course summary:

Below you will find, after each class, a brief summary of the topics covered in class. This should not be taken as a complete description of the course's content.


Introduction, parametric searching (slope selection), randomized halving, searching in sorted martices and applications, Clarkson-Shor (the diameter of a set of points in ), geometric local search (a PTAS for hitting a set of disks by points from P ), min dom set via local search for terrain-like graphs and for disk graphs (presented by Stav and Amit & Itamar), Welzl’s smallest enclosing disk algoritm (presented by Katya & Tamar), TSP – Christofides’ algorithm (presented by Omri & Ron), Arora’s algorithm (presented by Michael & Shaked).

 

 

 

Last update: January 8, 2020