Titlebook: Kombinatorische Optimierung; Theorie und Algorith Bernhard Korte,Jens Vygen Textbook 20122nd edition Springer-Verlag Berlin Heidelberg 2012

泥瓦匠

2731-3557 und umfassende Literaturangaben. .Diese zweite deutsche Auflage enthält alle Ergänzungen und Aktualisierungen der fünften englischen Auflage, darunter mehr als 60 neue Übungsaufgaben. Sie gibt den neuesten Stand der Kombinatorischen Optimierung wieder..978-3-642-25401-7Series ISSN 2731-3557 Series E-ISSN 2731-3565

inscribe

,Einführung,tellt, möchte sie erreichen, dass die Maschine jede Leiterplatte möglichst schnell fertig stellt. Die Bohrzeit selbst können wir nicht verringern, wohl aber die von der Maschine verbrauchte Zeit, um zu den Bohrpunkten zu kommen. Meist verfügen Bohrmaschinen über zwei verschiedene Bewegungsrichtungen

CRUE

Lineare Optimierung,n jedoch nicht als eine umfassende Einführung in die lineare Optimierung betrachtet werden. Dem mit der linearen Optimierung nicht vertrauten Leser seien die am Ende des Kapitels angegebenen Texte empfohlen.

共同生活

,Aufspannende Bäume und Arboreszenzen,Städte verbindet. Die zu mietenden Kabelverbindungen sollen alle Städte auf die billigste Weise miteinander verbinden. Dieses Problem stellt man natürlich durch einen Graphen dar: Die Knoten sind die Städte und die Kanten die Kabelverbindungen. Nach Satz 2.4 sind die minimalen zusammenhängenden aufs

青春期

CARE

Gewichtete Matchings, sein. Wir werden EDMONDS’ KARDINALITÄTS-MATCHING-ALGORITHMUS für den gewichteten Fall erweitern und eine O (n3)-Implementierung angeben. Dieser Algorithmus hat diverse Anwendungen, von denen einige in den Aufgaben und in Abschnitt 12.2 vorgestellt werden.

雀斑

共同时代

Verallgemeinerungen von Matroiden, durch Weglassen des Axioms (M3). In Abschnitt 14.1 betrachten wir Greedoide; sie entstehen durch Weglassen des Axioms (M2) (anstatt von (M3)). Ferner gibt es gewisse mit Matroiden und submodularen Funktionen verwandte Polytope - so genannte Polymatroide - die zu starken Verallgemeinerungen von wich

是突袭

,NP-Vollständigkeit, jedoch auch viele wichtige Probleme, für die kein polynomieller Algorithmus bekannt ist. Obwohl wir nicht beweisen können, dass es diese nicht gibt, können wir aber zeigen, dass aus der Existenz eines polynomiellen Algorithmus für ein „schweres“ (genauer: NP-schweres) Problem die Existenz eines pol

POWER

Approximationsalgorithmen, betrachtet. In den verbleibenden Kapiteln werden wir einige Strategien zur Handhabung von NP-schweren kombinatorischen Optimierungsproblemen besprechen. An erster Stelle stehen hier die Approximationsalgorithmen.