Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2000 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Combinatorial Optimization

Theory and Algorithms

verfasst von: Bernhard Korte, Jens Vygen

Verlag: Springer Berlin Heidelberg

Buchreihe : Algorithms and Combinatorics

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Combinatorial optimization is one of the youngest and most active areas of discrete mathematics, and is probably its driving force today. It became a subject in its own right about 50 years ago. This book describes the most important ideas, theoretical results, and algo­ rithms in combinatorial optimization. We have conceived it as an advanced gradu­ ate text which can also be used as an up-to-date reference work for current research. The book includes the essential fundamentals of graph theory, linear and integer programming, and complexity theory. It covers classical topics in combinatorial optimization as well as very recent ones. The emphasis is on theoretical results and algorithms with provably good performance. Applications and heuristics are mentioned only occasionally. Combinatorial optimization has its roots in combinatorics, operations research, and theoretical computer science. A main motivation is that thousands of real-life problems can be formulated as abstract combinatorial optimization problems. We focus on the detailed study of classical problems which occur in many different contexts, together with the underlying theory. Most combinatorial optimization problems can be formulated naturally in terms of graphs and as (integer) linear programs. Therefore this book starts, after an introduction, by reviewing basic graph theory and proving those results in linear and integer programming which are most relevant for combinatorial optimization.

Inhaltsverzeichnis

Frontmatter
1. Introduction
Abstract
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 L ∞-distance. (Older machines can only move either horizontally or vertically at a time; in this case the adjusting time is proportional to the L 1-distance, the sum of the horizontal and the vertical 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
There are basically three types of algorithms for Linear Programming: 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.
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 digraph:
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)→+ ℝ+ 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 3)-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 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 the general 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.
Bernhard Korte, Jens Vygen
13. Matroids
Abstract
Many combinatorial optimization problems can be formulated as follows. Given a set system (E, F), i.e. a finite set E and someF ⊆ 2 E , and a cost function c: F → ℝ, find an element of F whose cost is minimum or maximum. In the following we assume that c is a modular set function, i.e. we have c: E → ℝ and 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. Finally, in Section 14.3 we consider the problem of minimizing an arbitrary submodular function. This can be done in polynomial time with the Ellipsoid Method. For the important special case of symmetric submodular functions we mention a simple combinatorial algorithm.
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.
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 G with capacities u, 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.
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.41). 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
Backmatter
Metadaten
Titel
Combinatorial Optimization
verfasst von
Bernhard Korte
Jens Vygen
Copyright-Jahr
2000
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-21708-5
Print ISBN
978-3-662-21710-8
DOI
https://doi.org/10.1007/978-3-662-21708-5