COMBINATORIAL OPTIMIZATION
ENUMERATION RUNNING TIME OF ALGORITHMS LINEAR OPTIMIZATION PROBLEMS SORTING EXERCISES REFERENCES 2 GRAPHS BASIC DE?NITIONS TREES, CIRCUITS, AND CUTS CONNECTIVITY EULERIAN AND BIPARTITE GRAPHS PLANARITY PLANAR DUALITY 3 LINEAR PROGRAMMING POLYHEDRA THE SIMPLEX ALGORITHM DUALITY CONVEX HULLS AND POLYTOPES 4 LINEAR PROGRAMMING ALGORITHMS SIZE OF VERTICES AND FACES CONTINUED FRACTIONS GAUSSIAN ELIMINATION THE ELLIPSOID METHOD KHACHIYAN’S THEOREM SEPARATION AND OPTIMIZATION 5 INTEGER PROGRAMMING THE INTEGER HULL OF A POLYHEDRON UNIMODULAR TRANSFORMATIONS TOTAL DUAL INTEGRALITY TOTALLY UNIMODULAR MATRICES CUTTING PLANES LAGRANGEAN RELAXATION 6 SPANNING TREES AND ARBORESCENCES MINIMUM SPANNING TREES MINIMUM WEIGHT ARBORESCENCES POLYHEDRAL DESCRIPTIONS PACKING SPANNING TREES AND ARBORESCENCES 7 SHORTEST PATHS SHORTEST PATHS FROM ONE SOURCE SHORTEST PATHS BETWEEN ALL PAIRS OF VERTICES MINIMUM MEAN CYCLES 8 NETWORK FLOWS MAX-FLOW-MIN-CUT THEOREM MENGER’S THEOREM THE EDMONDS-KARP ALGORITHM BLOCKING FLOWS AND FUJISHIGE’S ALGORITHM THE GOLDBERG-TARJAN ALGORITHM GOMORY-HU TREES THE MINIMUM CUT IN AN UNDIRECTED GRAPH 9 MINIMUM COST FLOWS PROBLEM FORMULATION AN OPTIMALITY CRITERION MINIMUM MEAN CYCLE-CANCELLING ALGORITHM SUCCESSIVE SHORTEST PATH ALGORITHM ORLIN’S ALGORITHM FLOWS OVER TIME 10 MAXIMUM MATCHINGS 10 1 BIPARTITE MATCHING 10 2 THE TUTTE MATRIX 10 3 TUTTE’S THEOREM 10 4 EAR-DECOMPOSITIONS OF FACTOR-CRITICAL GRAPHS 10 5 EDMONDS’ MATCHING ALGORITHM 11 WEIGHTED MATCHING 11 1 THE ASSIGNMENT PROBLEM 11 2 OUTLINE OF THE WEIGHTED MATCHING ALGORITHM 11 3 IMPLEMENTATION OF THE WEIGHTED MATCHING ALGORITHM 11 4 POSTOPTIMALITY 11 5 THE MATCHING POLYTOPE 12 B-MATCHINGS AND T -JOINS 12 1 B-MATCHINGS 12 2 MINIMUM WEIGHT T -JOINS 12 3 T -JOINS AND T -CUTS 12 4 THE PADBERG-RAO THEOREM 13 MATROIDS 13 1 INDEPENDENCE SYSTEMS AND MATROIDS 13 2 OTHER MATROID AXIOMS 13 3 DUALITY 13 4 THE GREEDY ALGORITHM 13 5 MATROID INTERSECTION 13 6 MATROID PARTITIONING 13 7 WEIGHTED MATROID INTERSECTION 14 GENERALIZATIONS OF MATROIDS 14 1 GREEDOIDS 14 2 POLYMATROIDS 14 3 MINIMIZING SUBMODULAR FUNCTIONS 14 4 SCHRIJVER’S ALGORITHM 14 5 SYMMETRIC SUBMODULAR FUNCTIONS 15 NP-COMPLETENESS 15 1 TURING MACHINES 15 2 CHURCH’S THESIS 15 3 P AND NP 15 4 COOK’S THEOREM 15 5 SOME BASIC NP-COMPLETE PROBLEMS 15 6 THE CLASS CONP 15 7 NP-HARD PROBLEMS 16 APPROXIMATION ALGORITHMS 16 1 SET COVERING 16 2 COLOURING 16 3 APPROXIMATION SCHEMES 16 4 MAXIMUM SATIS?ABILITY 16 5 THE PCP THEOREM 16 6 L-REDUCTIONS 17 THE KNAPSACK PROBLEM 17 1 FRACTIONAL KNAPSACK AND WEIGHTED MEDIAN PROBLEM 17 2 A PSEUDOPOLYNOMIAL ALGORITHM 17 3 A FULLY POLYNOMIAL APPROXIMATION SCHEME 18 BIN-PACKING 18 1 GREEDY HEURISTICS 18 2 AN ASYMPTOTIC APPROXIMATION SCHEME 18 3 THE KARMARKAR-KARP ALGORITHM 19 MULTICOMMODITY FLOWS AND EDGE-DISJOINT PATHS 19 1 MULTICOMMODITY FLOWS 19 2 ALGORITHMS FOR MULTICOMMODITY FLOWS 19 3 DIRECTED EDGE-DISJOINT PATHS PROBLEM 19 4 UNDIRECTED EDGE-DISJOINT PATHS PROBLEM 20 NETWORK DESIGN PROBLEMS 20 1 STEINER TREES 20 2 THE ROBINS-ZELIKOVSKY ALGORITHM 20 3 SURVIVABLE NETWORK DESIGN 20 4 A PRIMAL-DUAL APPROXIMATION ALGORITHM 20 5 JAIN’S ALGORITHM 21 THE TRAVELING SALESMAN PROBLEM 21 1 APPROXIMATION ALGORITHMS FOR THE TSP 21 2 EUCLIDEAN TSPS 21 3 LOCAL SEARCH 21 4 THE TRAVELING SALESMAN POLYTOPE 21 5 LOWER BOUNDS 21 6 BRANCH-AND-BOUND 22 FACILITY LOCATION 22 1 THE UNCAPACITATED FACILITY LOCATION PROBLEM 22 2 ROUNDING LINEAR PROGRAMMING SOLUTIONS 22 3 PRIMAL-DUAL ALGORITHMS 22 4 SCALING AND GREEDY AUGMENTATION 22 5 BOUNDING THE NUMBER OF FACILITIES 22 6 LOCAL SEARCH 22 7 CAPACITATED FACILITY LOCATION PROBLEMS 22 8 UNIVERSAL FACILITY LOCATION