Geometric Optimization (Fall 2013)

مرجع: http://www.cs.tau.ac.il/~michas/optcourse.html

استاد: Sharir

The syllabus of the course 

===== 

The syllabus may not exactly coincide with the material that will be taught. It will be (slightly) updated during the semester 

===== 

(1) Parametric Searching:

The basic technique

Illustration: Slope selection

Issues in parallel computation

Cole's improvement

Alternatives: Probabilistic approach, Expanders, Monotone Matrix Searching, Chan's technique

===== 

(2) Linear Programming: Geometric Approach:

Review of Megiddo's algorithm and Seidel's randomized algorithm. Algorithms by Clarkson and by Matousek et al.

Abstract linear programming: Framework, geometric applications, variants

===== 

(3) Search in Monotone Matrices: 

===== 

(4) Facility Location:

The p-center probolem

Efficient algorithm for the 2-center problem

Exact and approximate algorithms for the general case

Clustering

The p-median problem and other variants

===== 

(5) Diameter in Three Dimensions:

A randomized algorithm

A deterministic algorithm

===== 

(6) Geometric Optimization and Arrangements:

Hausdorff distances

Width in three dimensions

Polygon placements; biggest stick in a polygon.

===== 

(7) Shortest Paths:

Shortest paths in the plane

Shortest paths on a convex polytope and in polyhedral 3-D regions

Approximate shortest paths

===== 

(8) Approximation Algorithms for Geometric Optimization:

Euclidean travelling salesperson

Approximating diameter, width, minimum-width annuli and cylinders

===== 

(9) Approximate Nearest Neighbor Search in Higher Dimensions:

Review of recent techniques