16:198:522:01 -- NETWORK & COMBINATORIAL OPTIMIZATION ALGORITHMS
Instructor: Michael D. Grigoriadis, CoRE
308,
1-732-445-2001 Ext.2898; Off.Hrs: T 11:45-1:45pm. Email:
TA: Jihui Zhao, Hill Center 403, (732) 445-2001 Ext 9565,
Email: zhaojih (at) cs (dot) rutgers (dot) edu. OHrs: M&W 2:00-3:30 pm.
Purpose:
Introduction and systematic study of classes of
discrete optimization problems that arise as theoretical or
practical applications,
of the underlying combinatorial optimization theory, and the
analysis and design of efficient algorithms for their exact or
approximate solution. The content
is intended for students in
computer science and in other disciplines such as mathematics,
statistics, operations research, engineering, and bioinformatics.
Prereqs:
DCS graduate admission requirements;
background in design and analysis of algorithms.
Expected work:
Four problem sets and a {\bf final exam (Tuesday May 6, 3-6pm; Hill 120)}.
Topics:
--Brief review: NP-Completeness
and problem reductions. Elements of classical network optimization,
LP duality, primal dual schema, shortest paths & negative cycles,
Karp's min-mean cycle algorithm, cost-to-time ratio problems.
--Flows:
Flow decomposition, max-flow min-cut duality and
integrality theorems;
augmenting path and preflow push algorithms.
Scaling; dynamic trees; parametric minimum s,t-cuts.
Combinatorial implications:
disjoint paths (Menger), bipartite matchings and
vertex covers (Kvnig-Egervary), optimal closures.
--Extensions: Lower bounds, Hoffman's
feasible circulation, min-flow max-cut and
Dilworth's theorems; scheduling and network connectivity. All pairs
min
s,t cuts, Gomory-Hu trees, fast deterministic and randomized global
minimum cut
algorithms. Multiterminal network synthesis.
--Min-cost
flows:
polynomial primal, dual and primal dual algorithms; cycle canceling,
sequential
SPs, capacity and cost scaling.
Bipartite weighted matching.
--Multicommodity flows.
Integer and
fractional flows; optimal routing and network design application. Duality and sparsest
cuts. Recent
results.
--Matching:
Systems of distinct representatives; problem reductions;
alternating paths and trees. Birkhoff-von
Neumann, Kvnig-Egervary, Mendelsohn-Dulmage theorems. Max-min,
Gilmore-Gomory,
Gale-Shapley matchings.
--Nonbipartite weighted matching:
Tutte-Berge formula, Edmonds-Gallai decomposition, Edmonds' blossom
algorithm,
proofs. T-joins, postman tours, b-matching, Euclidean
matching.
Approximate TSP tours.
Approximation algorithms
for several NP-hard
problems, based
on greedy, primal-dual and LP rounding techniques.
(Note:
The exact list of topics covered in a semester may differ somewhat
from the above.)
Sources:
Notes, recent research papers and chapters from:
Network Flows by Ahuja, Magnanti and
Orlin, Prentice Hall (1993);
Combinatorial
Optimization,
Polyhedra and Efficiency by A. Schrijver, 3 volumes, Springer
(2003); Combinatorial Optimization by
Cook et al.,
Wiley (1997);
Approximation Algorithms by V.Vazirani, Springer (2001).
Other useful books
are
by Kleinberg & Tardos (2005);
by Tarjan (paperback, 1983), Hochbaum (Ed., 1997), Papadimitriou &
Stieglitz
(1982), Lawler (1976), Schrijver (paperback
1986), and the "classics": Ford&Fulkerson's
Network Flows (1962), and Lovasz & Plummner's Matching
Theory (1986).
Which book to buy? Theoreticians and discrete
optimizers: Consider
Schrijver's 3-volume reference (a bit high level, but
it's a steal!); The Ahuja et al. book is easier to read,
has most network flow algorithms, lots of models,
applications and
exercises (list price a bit high);
the Cook et al. book is also a worthwhile choice;
Vazirani's book deals with NP-hard approximation algorithms.
Check prices because they vary widely!
We will have several of them on reserve at the Math
Library, Hill Center.
Grading guideline:
0.25HW + 0.75FIN, (where FIN=0 if Final Exam is missed).
Policies:
Final Examination: No Makeups.
Class attendance: Required;
Class participaton: Expected;
On homework You may collaborate
with others but you must: a) write your own solution separately and
unaided, b) List each collaborator or write "no collaboations" for
each problem, c) cite all sources, and d) you may not search out
solutions from previous years, from other courses,or from other
universities. Late HW: 33% penalty for the first week and
100% thereafter.
Academic Integrity:
Required reading!
Optional practice computing:
To gain experience with practical aspects of combinatorial
optimization
you may do 1-2 exercises (for extra credit).
For
example, you may code up an FPTAS we studied in class and study how
its error
behaves on a given class of
instances
versus lower bounds or versus an "exact" integer solution. You may use Matlab (primer)
and ILOG's CPLEX to do
such
tasks. Both are
accessible on our
DCS grad machines.
RU links: Academic
Calendar, Registrar's
pages, Status.