Gems of CombinatorialOptimization andGraph Algorithms




介绍
This book is intended as an homage to Prof. Rolf H. Möhring, an accomplished
leader in the field of combinatorial optimization and graph algorithms. We contacted
his former advisees who have successfully launched their own academic
careers. We asked them each to pick a topic that they thought would be both
interesting and accessible to a wide audience with a basic knowledge of graphs,
algorithms, and optimization. The result is this collection of beautiful results.
The reader can learn about the connection between shortest paths and mechanism
design, about the interplay of priority rules in scheduling and the existence of
pure-strategy Nash equilibria in weighted congestion games, about the critical role
played by matroids in the existence of pure-strategy Nash equilibria in
resource-buying games, about some geometric commonality between proportional
resource allocation and selfish flows, about using the gasoline puzzle and the
adjacency structure of the matching polytope to solve the budgeted matching
problem, about the relation between the knotting graph and the linear structure of
graphs, about convex programming relaxations and randomized rounding in
scheduling, about the significance of motifs in network analysis, about the analogy
between contraction hierarchies used for fast shortest path computations and
(perfect) elimination orderings in graphs, about universally good algorithms for the
knapsack problem with varying capacity and for a scheduling problem, about the
pivotal role of Hanan grids for the minimum Steiner tree problem for rectilinear
distances, about a linear-time algorithm that computes the longest tour for points in
the plane under the taxicab distance, and about a characterization of certain rectangular
dissections with surprising applications.
Each chapter can easily be used as the basis for a lecture or two in an advanced
undergraduate course or in a graduate course on graph algorithms, combinatorial
optimization, algorithmic game theory, or computational geometry. For improved
readability, citations within a chapter are kept to a minimum, but each chapter
concludes with a discussion of the relevant literature and provides pointers for
further reading.