\documentstyle[german,a4wide]{article}
\pagestyle{empty}

\begin{document}
\parindent0cm
\parskip2mm

\begin{center}
\huge \bf Seminar WS1996/97 \\
Approximationsalgorithmen f\"ur NP-harte Probleme
\end{center}

\section{Einf\"uhrung}

\begin{itemize}
\item R. Motwani, {\sl Lecture Notes on Approximation Algorithms}, Stanford University, 1992, Chapter 1
(ohne Multiprocessor Scheduling und Traveling Salesman Problem)
\end{itemize}

\section{Traveling Salesman Problem}

\begin{itemize}
\item D.S. Johnson, C.H. Papadimitriou, {\sl Performance guarantees for heuristics}, Chapter 5 (Sect. 1-4) in: Lawler, Lenstra, Rinnooy Kan, Shmoys (Ed.): {\sl The Traveling Salesman Problem}, John Wiley \& Sons, 1985
\end{itemize}

\section{Computing Near Optimal Schedules}

\begin{itemize}
\item J.K. Lenstra, D.B. Shmoys, {\sl Computing near-optimal schedules}, manuscript 1994
\item D.B. Shmoys, {\sl Computing Near-Optimal Solutions to Combinatorial Optimization Problems}, Sect. 5, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. ???, 1995
\end{itemize}

\section{Weighted Vertex Cover Problem}

\begin{itemize}
\item D.B. Shmoys, {\sl Computing Near-Optimal Solutions to Combinatorial Optimization Problems}, Sect. 2, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. ???, 1995
\item  R. Motwani, {\sl Lecture Notes on Approximation Algorithms}, Stanford University, 1992, Chapter 4.1 \& 4.2
(ohne randomisierte Algorithmen)
\end{itemize}

\section{Primal Dual Method for Approximation Algorithms I}

\begin{itemize}
\item M. Goemans, D. Williamson, Chapt. 4.1 -- 4.3 in: D. Hochbaum (Ed.), {\sl Approximation Algorithms for NP-Hard Problems}, PWS Publishing, 1996
\end{itemize}

\section{Primal Dual Method for Approximation Algorithms II}

\begin{itemize}
\item M. Goemans, D. Williamson, Chapt. 4.1 -- 4.3 in: D. Hochbaum (Ed.), {\sl Approximation Algorithms for NP-Hard Problems}, PWS Publishing, 1996
\end{itemize}

\section{Shortest Superstring Problem}

\begin{itemize}
\item A. Blum, T. Jiang, M. Li, J. Tromp, M. Yannakakis, {\sl Linear Approximation of Shortest Superstrings}, JACM, Vol. 41, No. 4, July 1994, 630 -- 647
\item D. Hochbaum, Chapt. 9.2.2 in: D. Hochbaum (Ed.), {\sl Approximation Algorithms for NP-Hard Problems}, PWS Publishing, 1996
\end{itemize}

\section{Multiple Sequence Alignment}

\begin{itemize}
\item R. Ravi, J.D. Kececioglou, {\sl Approximation Algorithms for Multiple Sequence Alignment}, 6th Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 937, 330 -- 339, Springer-Verlag, 1995
\end{itemize}

\section{Bottleneck Problems}

\begin{itemize}
\item D. Hochbaum, D.B. Shmoys, {\sl A unified approach to approximation algorithms for bottleneck problems}, JACM 33:3, July 1986, 533 -- 550
\item D. Hochbaum, Chapt. 9.4 in: D. Hochbaum (Ed.), {\sl Approximation Algorithms for NP-Hard Problems}, PWS Publishing, 1996
\end{itemize}

\section{Maximum Satisfiability}

\begin{itemize}
\item  D.B. Shmoys, {\sl Computing Near-Optimal Solutions to Combinatorial Optimization Problems}, Sect. 3, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. ???, 1995
\item J. Chen, {\sl Lecture Notes in Computational Optimization}, Sect. 31, Texas A \& M University, 1995
\item Yannakakis, {\sl On the approximation of maximum satisfiability}, 3rd Symposium on Discrete Algorithms, 1992, 1 -- 9 (also: Journal of Algorithms, Vol. 17, 1994)
\end{itemize}

\section{MAXSNP Completeness}

\begin{itemize}
\item Papadimitriou, Yannakakis, {\sl Optimization, Approximation and Complexity Classes}, Journal of Computer and System Sciences, Vol. 43, 1991, 425 -- 440
\item Papadimitriou, {\sl Computational Complexity}, Chapt. 13.2, Addison Wesley 1994
\end{itemize}

\section{Hardness of Approximation}

\begin{itemize}
\item  J. Chen, {\sl Lecture Notes in Computational Optimization}, Sect. 32 + 33, Texas A \& M University, 1995
\item  D.B. Shmoys, {\sl Computing Near-Optimal Solutions to Combinatorial Optimization Problems}, Sect. 1, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. ???, 1995
\end{itemize}

\section{Approximationsschemata}

\begin{itemize}
\item R. Motwani, {\sl Lecture Notes on Approximation Algorithms}, Stanford University, 1992, Chapter 2.1 -- 2.3
\item D. Hochbaum, Chapt. 9.3.1 in: D. Hochbaum (Ed.), {\sl Approximation Algorithms for NP-Hard Problems}, PWS Publishing, 1996 
\item J. Chen, {\sl Lecture Notes in Computational Optimization}, Sect. 15 + 16, Texas A \& M University, 1995
\end{itemize}

\section{Pseudopolynomial Algorithms}

\begin{itemize}
\item R. Motwani, {\sl Lecture Notes on Approximation Algorithms}, Stanford University, 1992, Chapter 2.4 -- 2.5
\item J. Chen, {\sl Lecture Notes in Computational Optimization}, Sect. 17 + 18, Texas A \& M University, 1995
\end{itemize}

\section{PAS for bin-packing}

\begin{itemize}
\item R. Motwani, {\sl Lecture Notes on Approximation Algorithms}, Stanford University, 1992, Chapter 3.1
\end{itemize}

\section{FPAS for bin-packing}

\begin{itemize}
\item R. Motwani, {\sl Lecture Notes on Approximation Algorithms}, Stanford University, 1992, Chapter 3.2 + 3.3
\item D. Hochbaum, Chapt. 9.5.1 in: D. Hochbaum (Ed.), {\sl Approximation Algorithms for NP-Hard Problems}, PWS Publishing, 1996 
\end{itemize}

\medskip

\section*{Einf\"uhrungen}

\begin{itemize}
\item Ran Libeskind-Hadas, {\sl Approximation Algorithms: Good Solutions to Hard Problems}, American Mathematical Monthly, Vol. 102, No. 1, Jan. 1995, 57 -- 61
\item Cormen, Leiserson, Rivest, {\sl Introduction to Algorithms}, MIT Press / McGraw-Hill, 1990, Chapters 36 + 37
\end{itemize}

\end{document}



