\documentstyle{article}
\begin{document}
\bibliographystyle{alpha}
\title{A Reading List in Combinatorial Optimization
\footnote{\copyright 1994 by Brian Borchers.
This article may be freely duplicated and distributed so long as no 
consideration is received in return, and this copyright notice remains
intact.}}  

\date{April 21, 1994}
\author{Brian Borchers}
\maketitle

\tableofcontents

\begin{abstract}
This document is a bibliography of books and survey articles
on various topics in combinatorial optimization and integer programming. 
I've tried to limit this bibliography primarily to books and survey papers, 
because there are far more research papers on each of these topics than
I could ever hope to include in this bibliography.  Hopefully, the 
papers and books that I have included will point the reader to important
research papers in each topic.

This bibliography can be obtained via gopher or anonymous ftp from the 
Mathematics Archives at archives.math.utk.edu.  
I'd like to expand and improve on this bibliography--  If you have any 
entries or additional areas that you'd like to see included in the 
bibliography, please send your comments to me 
(borchers@nmt.edu).
\end{abstract}

Textbooks that cover a broad range of topics in combinatorial optimization
include 
\cite{Foulds:combopt,Lawler:combopt,NW:icopt,PR:discopt,PS:combopt,SM:foundations,Sch:theory}.  
The book by Papadimitriou and Steiglitz is 
a good choice for a first course in combinatorial optimization.  Unfortunately,
it is currently out of print.  The book by Nemhauser and Wolsey is a good 
choice for more advanced students, but I wouldn't use it for a first course
in combinatorial optimization.  I also like the book by Parker and 
Rardin, but its coverage of some topics is limited. 

Computational Complexity theory plays an important role in combinatorial
optimization, separating the easy problems that can be solved in polynomial
time from the hard (particularly ``NP-Hard'') problems for which no polynomial
time algorithms are known.  Books on this topic include \cite{GJ:candi,Papa:complexity}.  

The first combinatorial optimization problems to be extensively studied
were problems on graphs, including the shortest path problem, max flow 
problems, and matching.  Books on this topic include 
\cite{AMO:flows,Bertsekas:flows,GKP:flows,Lawler:combopt}.

Many combinatorial optimization problems can be formulated as integer 
programming problems.  In formulating an integer programming problem,
there are many tricks that can be used to make the problem easier to 
solve.  Books and articles on the formulation of integer
programming and mixed integer programming problems include 
\cite{AD:lessons,BJNSV:formulate,Williams:models}.  

Branch and bound 
algorithms are commonly used to solve integer programming problems.  
Branch and bound algorithms are discussed in nearly all of the textbooks
described above, including 
\cite{NW:icopt,PR:discopt,PS:combopt,SM:foundations}.  
Branch and bound and dynamic programming 
algorithms for the knapsack problem are discussed in \cite{MT:knapsack}.

Cutting plane 
algorithms are another approach to integer programming problems.  
These are described in \cite{NW:icopt,PR:discopt,PS:combopt,SM:foundations}.  
Early
cutting plane algorithms such as Gomory's cutting plane algorithm have not
proven to be very effective.  However, recent work in problem specific cutting
plane algorithms and algorithms that combine branch and bound with cutting
planes has been somewhat more successful.  Some 
recent examples of cutting plane techniques include 
\cite{Junger:asp,Lawler:tour,PR:bandc,Stoer:design}.    Some theoretical
material on cutting planes can be found in \cite{GLS:geometric,Sch:theory}.

Heuristics for combinatorial optimization problems are algorithms that
find ``good'' solutions without any guarantee that the solutions are
optimal.  In recent years, there has been a lot of interest in heuristics, 
including genetic algorithms \cite{Davis:genandsim,Davis:handbook,Goldberg:genetic}, 
simulated annealing \cite{AK:anneal,AVL:simulated,Davis:genandsim,Reeves:modern}, 
and tabu search
\cite{Glover:tutorial,Glover:tabuI,Glover:tabuII,Reeves:modern,MF:heuristics}.

Approximation schemes are algorithms that are guaranteed to produce a 
solution that is within $\epsilon$ of optimality.  Of particular
interest are polynomial time approximation schemes-  algorithms that given
$\epsilon$ find 
an answer within a factor $\epsilon$ of optimality while running in 
polynomial time.  
Some approximation 
schemes for NP-hard problems are discussed in
\cite{PS:combopt,PR:discopt,HS:algorithms}.  
Unfortunately, there are also many NP-hard problems for which such
approximation schemes are impossible unless P=NP.
Some negative results are 
discussed in \cite{PS:combopt,PR:discopt}.  Very recently, work on
transparent proofs has resulted in a large number of theorems about
the non existence of polynomial time approximation schemes for various
problems.  These are discussed briefly
in \cite{babai:hard,Johnson:tale}.  

Algorithms and data structures are particularly important in implementing
techniques for combinatorial optimization.  Backtracking and dynamic
programming are among the important algorithmic issues.  Good implementations
of data structures such as priority queues are important in getting good
performance from the algorithms.  
Books that discuss these
issues include 
\cite{CLR:algorithms,HS:algorithms,Hu:algorithms,Tarjan:algorithms}.

Scheduling problems are an important area of research in combinatorial
optimization.  Some books on this topic include \cite{Blaz:scheduling,Coffman:scheduling,Hu:algorithms}.

Matroids are a kind of algebraic structure within which some combinatorial
optimization problems can easily be solved.  Matroids are discussed in 
\cite{Lawler:combopt,Oxley:matroids,NW:icopt,PS:combopt,PR:discopt}.
Greedoids, an extension of matroids, are described in \cite{KLS:greedoids}.

One interesting approach to integer programming problems is basis reduction.
This is discussed in \cite{GLS:geometric,NW:icopt,SM:foundations,Sch:theory}.

Duality in integer
programming is another of research.  This topic is discussed in
\cite{Fisher:lagrange,NW:icopt,PR:discopt,Shapiro:lagrange}.

There are a number of collection of test problems in combinatorial 
optimization that can be obtained via anonymous FTP.  These include
\cite{beasley:orlib,BBI:miplib,Reinelt:tsplib}.  

Finally, a very useful, but slightly out of date annotated bibliography 
can be found in \cite{OLR:biblio}.
\newpage
\bibliography{readings}
\end{document}



