Combinatorial Optimization

Frontmatter

1. Introduction

Abstract

Let us start with two examples.

A company has a machine which drills holes into printed circuit boards. Since it produces many of these boards it wants the machine to complete one board as fast as possible. We cannot optimize the drilling time but we can try to minimize the time the machine needs to move from one point to another. Usually drilling machines can move in two directions: the table moves horizontally while the drilling arm moves vertically. Since both movements can be done simultaneously, the time needed to adjust the machine from one position to another is proportional to the maximum of the horizontal and the vertical distance. This is often called the ℓ_∞-distance. (Older machines can only move either horizontally or vertically at a time; in this case the adjusting time is proportional to the ℓ₁-distance, the sum of the horizontal and the vertical distance.)

2. Graphs

Abstract

Graphs are a fundamental combinatorial structure used throughout this book. In this chapter we not only review the standard definitions and notation, but also prove some basic theorems and mention some fundamental algorithms.

3. Linear Programming

Abstract

In this chapter we review the most important facts about Linear Programming. Although this chapter is self-contained, it cannot be considered to be a comprehensive treatment of the field. The reader unfamiliar with Linear Programming is referred to the textbooks mentioned at the end of this chapter.

4. Linear Programming Algorithms

Abstract

There are basically three types of algorithms for Linear Programming: the Simplex Algorithm (see Section 3.2), interior point algorithms, and the Ellipsoid Method.

5. Integer Programming

Abstract

In this chapter, we consider linear programs with integrality constraints:

×

6. Spanning Trees and Arborescences

Abstract

Consider a telephone company that wants to rent a subset from an existing set of cables, each of which connects two cities. The rented cables should suffice to connect all cities and they should be as cheap as possible. It is natural to model the network by a graph: the vertices are the cities and the edges correspond to the cables. By Theorem 2.4 the minimal connected spanning subgraphs of a given graph are its spanning trees. So we look for a spanning tree of minimum weight, where we say that a subgraph T of a graph G with weights c : E(G) → ℝ has weight c(E(T))=∑ _e∈E(T) c(e).

7. Shortest Paths

Abstract

One of the best-known combinatorial optimization problems is to find a shortest path between two specified vertices of a digraph:

×

8. Network Flows

Abstract

In this and the next chapter we consider flows in networks. We have a digraph G with edge capacities u : E(G) → ℝ₊ and two specified vertices s (the source) and t (the sink). The quadruple (G, u, s, t) is sometimes called a network.

9. Minimum Cost Flows

Abstract

In this chapter we show how we can take edge costs into account. For example, in our application of the Maximum Flow Problem to the Job Assignment Problem mentioned in the introduction of Chapter 8 one could introduce edge costs to model that the employees have different salaries; our goal is to meet a deadline when all jobs must be finished at a minimum cost. Of course, there are many more applications.

10. Maximum Matchings

Abstract

Matching theory is one of the classical and most important topics in combinatorial theory and optimization. All the graphs in this chapter are undirected. Recall that a matching is a set of pairwise disjoint edges. Our main problem is:

×

11. Weighted Matching

Abstract

Nonbipartite weighted matching appears to be one of the “hardest” combinatorial optimization problems that can be solved in polynomial time. We shall extend Edmonds’ Cardinality Matching Algorithm to the weighted case and shall again obtain an O(n ³)-implementation. This algorithm has many applications, some of which are mentioned in the exercises and in Section 12.2. There are two basic formulations of the weighted matching problem:

×

12. b-Matchings and T-Joins

Abstract

In this chapter we introduce two more combinatorial optimization problems, the Minimum Weight b-Matching Problem in Section 12.1 and the Minimum Weight T-Join Problem in Section 12.2. Both can be regarded as generalizations of the Minimum Weight Perfect Matching Problem and also include other important problems. On the other hand, both problems can be reduced to the Minimum Weight Perfect Matching Problem. They have combinatorial polynomial-time algorithms as well as polyhedral descriptions. Since in both cases the Separation Problem turns out to be solvable in polynomial time, we obtain another polynomial-time algorithm for these generalized matching problems (using the Ellipsoid Method; see Section 4.6). In fact, the Separation Problem can be reduced to finding a minimum capacity T-cut in both cases; see Sections 12.3 and 12.4. This problem, finding a minimum capacity cut δ(X) such that |X∩T| is odd for a specified vertex set T, can be solved with network flow techniques.

13. Matroids

Abstract

Many combinatorial optimization problems can be formulated as follows. Given a set system \( (E,\mathcal{F}) \), i.e. a finite set E and some \( \mathcal{F} \subseteq 2^E \), and a cost function \( c {\text{: }}\mathcal{F} \to \mathbb{R} \), find an element of \( \mathcal{F} \) whose cost is minimum or maximum. In the following we consider modular functions c, i.e. assume that \( c{\text{(}}X{\text{)}} = c{\text{(0/) + }}\sum\nolimits_{x \in X} {{\text{(}}c(\{ x\} ) - c{\text{(0/)}})} \) for all \( X \subseteq E \); equivalently we are given a function c: E → ℝ and write c(X) = Σ_x∈X c(e).

14. Generalizations of Matroids

Abstract

There are several interesting generalizations of matroids. We have already seen independence systems in Section 13.1, which arose from dropping the axiom (M3). In Section 14.1 we consider greedoids, arising by dropping (M2) instead. Moreover, certain polytopes related to matroids and to submodular functions, called polymatroids, lead to strong generalizations of important theorems; we shall discuss them in Section 14.2. In Sections 14.3 and 14.4 we consider two approaches to the problem of minimizing an arbitrary submodular function: one using the Ellipsoid Method, and one with a combinatorial algorithm. For the important special case of symmetric submodular functions we mention a simpler algorithm in Section 14.5.

15. NP-Completeness

Abstract

For many combinatorial optimization problems a polynomial-time algorithm is known; the most important ones are presented in this book. However, there are also many important problems for which no polynomial-time algorithm is known. Although we cannot prove that none exists we can show that a polynomial-time algorithm for one “hard” (more precisely: NP-hard) problem would imply a polynomialtime algorithm for almost all problems discussed in this book (more precisely: all NP-easy problems).

16. Approximation Algorithms

Abstract

In this chapter we introduce the important concept of approximation algorithms. So far we have dealt mostly with polynomially solvable problems. In the remaining chapters we shall indicate some strategies to cope with NP-hard combinatorial optimization problems. Here approximation algorithms must be mentioned in the first place.

17. The Knapsack Problem

Abstract

The Minimum Weight Perfect Matching Problem and the Weighted Matroid Intersection Problem discussed in earlier chapters are among the “hardest” problems for which a polynomial-time algorithm is known. In this chapter we deal with the following problem which turns out to be, in a sense, the “easiest” NP-hard problem:

×

18. Bin-Packing

Abstract

Suppose we have n objects, each of a given size, and some bins of equal capacity. We want to assign the objects to the bins, using as few bins as possible. Of course the total size of the objects assigned to one bin should not exceed its capacity.

19. Multicommodity Flows and Edge-Disjoint Paths

Abstract

The Multicommodity Flow Problem is a generalization of the Maximum Flow Problem. Given a digraph with edge capacities, we now ask for an s-t-flow for several pairs (s, t) (we speak of several commodities), such that the total flow through any edge does not exceed the capacity. We specify the pairs (s, t) by a second digraph; for technical reasons we have an edge from t to s when we ask for an s-t-flow. Formally we have:

×

20. Network Design Problems

Abstract

Connectivity is a very important concept in combinatorial optimization. In Chapter 8 we showed how to compute the connectivity between each pair of vertices of an undirected graph. Now we are looking for subgraphs that satisfy certain connectivity requirements. The general problem is:

×

21. The Traveling Salesman Problem

Abstract

In Chapter 15 we introduced the Traveling Salesman Problem (TSP) and showed that it is NP-hard (Theorem 15.42). The TSP is perhaps the best-studied NP-hard combinatorial optimization problem, and there are many techniques which have been applied. We start by discussing approximation algorithms in Sections 21.1 and 21.2. In practice, so-called local search algorithms (discussed in Section 21.3) find better solutions for large instances although they do not have a finite performance ratio.

22. Facility Location

Abstract

Many economic decisions involve selecting and/or placing certain facilities to serve given demands efficiently. Examples include manufacturing plants, storage facilities, depots, warehouses, libraries, fire stations, hospitals, base stations for wireless services (like TV broadcasting or mobile phone service), etc. The problems have in common that a set of facilities, each with a certain position, has to be chosen, and the objective is to meet the demand (of customers, users etc.) best. Facility location problems, which occur also in less obvious contexts, indeed have numerous applications.

Backmatter