CIS6930: APPROXIMATION ALGORITHMS

Term: Fall 2005
Time: Tue 10:40am-11:30am, Thu 10:40am-12:35pm
Location: Turlington 2328
Office hours: Tue 11:30am-12:30pm, Thu 12:35-1:35pm
Professor: Alper Üngör
Catalogue number: 3993
Credit hours: 3

info announcements schedule projects references

Announcements

Schedule

Date Lecture Topic Assignments Speaker
Aug 25 Th Introduction, syllabus, course structure.
Vertex cover, greedy algorithm,
hardness of approximating TSP
[V03] Chapter 1
HW#0 out
[ps, pdf]
Alper
Aug 30 Tu Set cover, greedy algorithm, tight example
[V03] Chapter 2
HW#1 out
[ps, pdf]
Alper
Sep 1 Th Set cover with frequency f, layering algorithm,
shortest superstring
[V03] Chapter 2
  Alper
Sep 6 Tu Steiner tree, metric Steiner tree
[V03] Chapter 3
  Alper
Sep 8 Th Metric TSP; Minimum weight multiway cut
[V03] Chapter 3
HW#1 due
Alper
Sep 13 Tu minimum weight k-cut
[V03] Chapter 4
HW#1 graded
Alper
Sep 15 Th k-center
[V03] Chapter 5
[Reading: [V03] Chapter 6]
HW#2 out
[ps, pdf]
PA#1 out
[ps, pdf]
Alper
Sep 20 Tu Shortest superstring revisited
constant factor approximation
[V03] Chapter 7
HW#0 due
Alper
Sep 22 Th Knapsack problem, PTAS, FPTAS
[V03] Chapter 8
 
Alper
Sep 27 Tu Fully polynomial time approximation scheme
Pseudo polynomial time algorithms, strongly NP-hard
[V03] Chapter 8
HW#2 due
Alper
Sep 29 Th Bin packing, Asymptotic PTAS
[V03] Chapter 9
Proposals due
Alper
Oct 4 Tu Project discussions
[Reading: [V03] Chapter 10]
PA#1 due
HW#3 out [ps, pdf]
 
Oct 6 Th Projects (cont.), Triangulations HW#2 graded
Alper
Oct 11 Tu Euclidean TSP
[A03]; [V03] Chapter 11
PA#1 due
Alper
Oct 13 Th PA1 discussion, Minimum weight triangulation
[H97] Chapter 8
  Alper
Oct 18 Tu Minimum weight Steiner triangulation
[H97] Chapter 8, [E94]

Alper
Oct 20 Th Quality Steiner triangulation
HW#3 due Alper
Oct 25 Tu LP Duality, PA#2 discussion
[V03] Chapter 12
PA#2 out
Alper
Oct 27 Th Dual-fitting
[V03] Chapter 13
HW#3 graded
HW#4 out [ps, pdf]
Alper
Nov 1 Tu Approximate query processing  
Alin
Nov 3 Th Approximate query processing  
Alin
Nov 8 Tu Rounding, randomized rounding
[V03] Chapter 14
 
Alper
Nov 10 Th Half-integrality; Primal-dual schema
[V03] Chapters 14, 15
HW#5 out
[ps, pdf]
Alper
Nov 15 Tu Scheduling Unrelated Parallel Machines
[V03] Chapter 17
PA#2 due
Alper
Nov 17 Th Scheduling Unrelated Parallel Machines
[V03] Chapter 17
 
Alper
Nov 22 Tu Lagrangian Relaxation, Semi-definite programming
[V03] Chapters 24, 25
HW#5 due
Alper
Nov 24 Th THANKSGIVING BREAK
Nov 29 Tu Project presentations
 
Xiaochun, Heping, Nishant, Nely
Dec 1 Th Final exam
 
 
Dec 6 Tu Project presentations
 
Bala, Jianhua, Ravi, Henry

References

Books
[V03] V. Vazirani. Approximation Algorithms. Springer, 2003.
[H97] D.S. Hochbaum. Approximation Algorithms for NP-Hard Problems. PWS, 1997.
Surveys
[H05] S. Har-Peled. Geometric Approximation Algorithms, [book manuscript].
Papers
[A03] S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey. Math Programming, August 2003.
[E94] D. Eppstein Approximating the Minimum Weight Triangulation. Disc. Comp. Geom. 11:163-191, 1994.
[H00] K. Helsgaun. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. European Journal of Operational Research, 126 (1), 106-130 (2000).
Links
[L1] A compendium of NP optimization problems
[L2] ACM-SIGACT
[L3] Computing Science Journal Collections
[L4] Journals of ACM
[L5] Journals of SIAM

info announcements schedule projects references


Alper Üngör (ungor@cise.ufl.edu) May 2005