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.

Bernhard Korte, Jens Vygen

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.

Bernhard Korte, Jens Vygen

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.

Bernhard Korte, Jens Vygen

4. Linear Programming Algorithms

Abstract

Three types of algorithms for LINEAR PROGRAMMING had the most impact: the SIMPLEX ALGORITHM (see Section 3.​2), interior point algorithms, and the ELLIPSOID METHOD .

Bernhard Korte, Jens Vygen

5. Integer Programming

Abstract

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

Bernhard Korte, Jens Vygen

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) \rightarrow \mathbb{R}\) has weight c(E(T)) = ∑ _{e ∈ E(T)} c(e). We shall refer to c(e) also as the cost of e.

Bernhard Korte, Jens Vygen

7. Shortest Paths

Abstract

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

Bernhard Korte, Jens Vygen

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) \rightarrow \mathbb{R}_{+}\) and two specified vertices s (the source) and t (the sink). The quadruple (G, u, s, t) is sometimes called a network .

Bernhard Korte, Jens Vygen

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.

Bernhard Korte, Jens Vygen

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.

Bernhard Korte, Jens Vygen

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.

Bernhard Korte, Jens Vygen

12. b-Matchings and T-Joins

Abstract

In this chapter we introduce two more combinatorial optimization problems, the MAXIMUM 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.

Bernhard Korte, Jens Vygen

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: \mathcal{F}\rightarrow \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(X) = c(∅) + ∑ _{x ∈ X} (c({x}) − c(∅)) for all X ⊆ E; equivalently we are given a function \(c: E \rightarrow \mathbb{R}\) and write c(X) = ∑ _{e ∈ X} c(e).

Bernhard Korte, Jens Vygen

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. Finally, in Section 14.6, we discuss the problem of maximizing a submodular function.

Bernhard Korte, Jens Vygen

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 polynomial-time algorithm for almost all problems discussed in this book (more precisely: all NP-easy problems).

Bernhard Korte, Jens Vygen

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.

Bernhard Korte, Jens Vygen

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:

Bernhard Korte, Jens Vygen

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.

Bernhard Korte, Jens Vygen

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.

Bernhard Korte, Jens Vygen

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.

Bernhard Korte, Jens Vygen

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.43). 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.

Bernhard Korte, Jens Vygen

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.

Bernhard Korte, Jens Vygen

Backmatter