GERMAN

Approximative Algorithmen und Nichtapproximierbarkeit

By Klaus Jansen; Marian Margraf

Book information

Publisher
de Gruyter
Year
2008
ISBN
9783110203172, 9783110203165
Language
german
Format
PDF
Filesize
4 MB (3877469 bytes)
Pages
\520
Library
degruyter.com
Time added
2023-07-20 15:19:45

Description

Gegenstand dieses Lehrbuchs ist die Behandlung schwer lösbarer diskreter Optimierungsprobleme. Im ersten Teil werden schnelle Algorithmen vorgestellt, die solche Probleme näherungsweise lösen können. Der zweite Teil behandelt Komplexitätstheorie und Nichtapproximierbarkeit von Optimierungsproblemen. Das Lehrbuch enthält zudem zahlreiche Anwendungsbeispiele, Übungsaufgaben, Illustrationen und Abschnitte über Grundlagen wie etwa die Turingmaschine. Frontmatter Inhaltsverzeichnis Kapitel 1 Einführung Kapitel 2 Die Komplexitätsklassen P und NP Kapitel 3 Approximative Algorithmen mit additiver Güte Kapitel 4 Algorithmen mit multiplikativer Güte I: Zwei Beispiele Kapitel 5 Algorithmen mit multiplikativer Güte II: Graphenprobleme Kapitel 6 Algorithmen mit multiplikativer Güte III: Prozessoptimierung Kapitel 7 Algorithmen mit multiplikativer Güte IV: Packungsprobleme Kapitel 8 Approximationsschemata Kapitel 9 Vollständige Approximationsschemata Kapitel 10 Randomisierte Algorithmen Kapitel 11 Lineare Programmierung: Deterministisches und randomisiertes Runden Kapitel 12 Lineare Programmierung und Dualität Kapitel 13 Asymptotische polynomielle Approximationsschemata Kapitel 14 MIN JOB SCHEDULING Kapitel 15 Max-Min Resource Sharing Kapitel 16 Semidefinite Programmierung Kapitel 17 Komplexitätstheorie für Optimierungsprobleme Kapitel 18 Nichtapproximierbarkeit I Kapitel 19 PCP Beweissysteme Kapitel 20 Nichtapproximierbarkeit II Backmatter

Similar books

Die Kunst, alle animalischen und vegetabilischen Substanzen, nähmlich alle Gattungen Fleisch, Geflügel, Wildpret, Fische, Zugemüse, Küchen- und Arzneygewächse, Früchte, Sulzen, Säfte; ferner Bier, schon zum Genusse völlig bereiteten Kaffeh, Thee u.s.w., in voller Frische, Schmackhaftigkeit und eigenthümlicher Würze mehrere Jahre zu erhalten : eine der nützlichsten Erfindungen von H. Appert in Paris, die nicht allein für die kleinste Haushaltung ohne allen Kostenaufwand anwendbar, und deßwegen ein unentbehrlicher, noch nie gegebener Anhang zu allen Koch- und Wirthschaftsbüchern ist, sondern auch die größten nur denkbaren Vortheile für Hospitäler, Armeen, Flotten etc. etc. gewährt, und wegen ihrer Gemeinnützigkeit von der französischen Regierung mit 12.000 Franken belohnt wurde

Die Kunst, alle animalischen und vegetabilischen Substanzen, nähmlich alle Gattungen Fleisch, Geflügel, Wildpret, Fische, Zugemüse, Küchen- und Arzneygewächse, Früchte, Sulzen, Säfte; ferner Bier, schon zum Genusse völlig bereiteten Kaffeh, Thee u.s.w., in voller Frische, Schmackhaftigkeit und eigenthümlicher Würze mehrere Jahre zu erhalten : eine der nützlichsten Erfindungen von H. Appert in Paris, die nicht allein für die kleinste Haushaltung ohne allen Kostenaufwand anwendbar, und deßwegen ein unentbehrlicher, noch nie gegebener Anhang zu allen Koch- und Wirthschaftsbüchern ist, sondern auch die größten nur denkbaren Vortheile für Hospitäler, Armeen, Flotten etc. etc. gewährt, und wegen ihrer Gemeinnützigkeit von der französischen Regierung mit 12.000 Franken belohnt wurde

1832 · PDF

Geschichte des Rechtsstreits zwischen der ältern und jüngern Linie des Fürstenhauses Anhalt-Bernburg. Band 3, Abteilung 1 Commentar zu den Gründen des, den Beytritt der vertretenen Streitgenossen, zu der von den unvertretenen erhobenen Nichtigskeitsquerel, abweisenden ersten Instanzurtheils vom 25sten November 1820: Fortgesetze Betrachtungen über die Natur einer prozessualischen Streitgenossenschaft, und über die Untheilbarkeit eines Verfahrens und Urtheils, den der Untheilbarkeit der Thatsachen und des Streitgegenstandes

Geschichte des Rechtsstreits zwischen der ältern und jüngern Linie des Fürstenhauses Anhalt-Bernburg. Band 3, Abteilung 1 Commentar zu den Gründen des, den Beytritt der vertretenen Streitgenossen, zu der von den unvertretenen erhobenen Nichtigskeitsquerel, abweisenden ersten Instanzurtheils vom 25sten November 1820: Fortgesetze Betrachtungen über die Natur einer prozessualischen Streitgenossenschaft, und über die Untheilbarkeit eines Verfahrens und Urtheils, den der Untheilbarkeit der Thatsachen und des Streitgegenstandes

1822 · PDF

Oeconomia. Oder Haußbuch : Zum Calendario Oeconomico & perpetuo gehörig. 1 Darinnen begriffen vnnd außführlichen erkleret ist, Wie ein Hauswirth, nach dem ihn Gott der Allmechtige gesegnet, ferner seine Nahrung nechst Gott anstellen sol, auch fruchtbarlichen geniessen vnd gebrauchen : Alldieweil in solchem angezeigt wird, wie ein Haußwirth erstlich sein Gesinde wol regieren sol, hernach, von allerley sachen zur Haußhaltung gehörig, Als von Brawen, Backen, Bleichen, Weinbergern, Gärten, Höltzung, Ackerbaw, Viehzucht, Jagten, Fisch vnd Vogelfang, Endlich von einer Haußartzney oder Haußapotecken vor den gemeinen Man.

Oeconomia. Oder Haußbuch : Zum Calendario Oeconomico & perpetuo gehörig. 1 Darinnen begriffen vnnd außführlichen erkleret ist, Wie ein Hauswirth, nach dem ihn Gott der Allmechtige gesegnet, ferner seine Nahrung nechst Gott anstellen sol, auch fruchtbarlichen geniessen vnd gebrauchen : Alldieweil in solchem angezeigt wird, wie ein Haußwirth erstlich sein Gesinde wol regieren sol, hernach, von allerley sachen zur Haußhaltung gehörig, Als von Brawen, Backen, Bleichen, Weinbergern, Gärten, Höltzung, Ackerbaw, Viehzucht, Jagten, Fisch vnd Vogelfang, Endlich von einer Haußartzney oder Haußapotecken vor den gemeinen Man.

1600 · PDF

Neu-gefundenes Eden., Oder:, Aussführlicher Bericht von Sud- und Nord-Carolina, Pensilphania, Mary Land, & Virginia. : Entworffen durch zwey in dise Provintzen gemachten Reisen, Reiss-Journal, und ville Brieffen, dardurch der gegenwärtige Zustand diser Länderen warhafftig entdecket, und dem Nebenmenschen zu Gutem an Tag gelegt wird. Samt beygefügtem Anhang, oder freye Unterweisung zu dem verlohrnen, nun aber wieder gefundenen Lapide Philosophorum, dardurch man bald zur Vergnügung, und wahrer [sic] Reichthum gelangen kan

Neu-gefundenes Eden., Oder:, Aussführlicher Bericht von Sud- und Nord-Carolina, Pensilphania, Mary Land, & Virginia. : Entworffen durch zwey in dise Provintzen gemachten Reisen, Reiss-Journal, und ville Brieffen, dardurch der gegenwärtige Zustand diser Länderen warhafftig entdecket, und dem Nebenmenschen zu Gutem an Tag gelegt wird. Samt beygefügtem Anhang, oder freye Unterweisung zu dem verlohrnen, nun aber wieder gefundenen Lapide Philosophorum, dardurch man bald zur Vergnügung, und wahrer [sic] Reichthum gelangen kan

1737 · PDF

Der nordamerikanische Freistaat Texas : ein Handbuch für solche, die dahin, insbesondere aber nach dem der deutschen Colonisationsgesellschaft für Texas angehörigen, in der County Berar gelegenen Landbezirk auswandern wollen : Nachricht über due Geschichte, Verfassung, Lage, Klima, Beschaffenheit des Landes, Gewerbe, Ackerbau, Viehzucht, Handel, Verkehr, Zinsfuss, Strassen ... sodann die deutschen Colonisationsgesellschaft nebst ihrem Programme, so wie den durchaus nöthigen Belehrungen und Anweisungen der Auswanderer über die Vorbereitungen zur Reise, während derselben und im Lande selbst

Der nordamerikanische Freistaat Texas : ein Handbuch für solche, die dahin, insbesondere aber nach dem der deutschen Colonisationsgesellschaft für Texas angehörigen, in der County Berar gelegenen Landbezirk auswandern wollen : Nachricht über due Geschichte, Verfassung, Lage, Klima, Beschaffenheit des Landes, Gewerbe, Ackerbau, Viehzucht, Handel, Verkehr, Zinsfuss, Strassen ... sodann die deutschen Colonisationsgesellschaft nebst ihrem Programme, so wie den durchaus nöthigen Belehrungen und Anweisungen der Auswanderer über die Vorbereitungen zur Reise, während derselben und im Lande selbst

1848 · PDF

Internationales Wörterbuch der Lederwirtschaft / International Dictionary of the Leather and Allied Trades / Dictionnaire International des Cuirs et Peaux et de leurs Dérivés / Vocabulario Internacional de la Industria y del Comercio de Cueros / Vocabolario Internazionale dell’Industria e del Commercio del Cuoio / Международный кожевенно-технический словарь: Deutsch — Englisch — Französisch — Spanisch — Italienisch — Russisch / German — English — French — Spanish — Italian / Allemand — Anglais — Français — Espagnol — Italien / Alemán — Inglés — Francés — Español — Italiano / Tedesco — Inglese — Francese — Spagnolo — Italiano / на немецком — английском — французском — испанском итальянском — русском языках

Internationales Wörterbuch der Lederwirtschaft / International Dictionary of the Leather and Allied Trades / Dictionnaire International des Cuirs et Peaux et de leurs Dérivés / Vocabulario Internacional de la Industria y del Comercio de Cueros / Vocabolario Internazionale dell’Industria e del Commercio del Cuoio / Международный кожевенно-технический словарь: Deutsch — Englisch — Französisch — Spanisch — Italienisch — Russisch / German — English — French — Spanish — Italian / Allemand — Anglais — Français — Espagnol — Italien / Alemán — Inglés — Francés — Español — Italiano / Tedesco — Inglese — Francese — Spagnolo — Italiano / на немецком — английском — французском — испанском итальянском — русском языках

1968 · PDF

Bericht der Experten-Kommission über die physikalisch-chemische Untersuchung des Rheinwassers / Rapport de la commission des experts sur les analyses physico-chimiques de l’eau du Rhin: 1. Serie Juni 1953 bis Juni 1954 ausgearbeitet vom Sekretariat der Kommission unter der Leitung von Herrn Dr. F. Zehender, Zürich, und von der Kommission der Delegierten genehmigt in der Sitzung vom 14. bis 17. September 1955 in Strassburg / lère série juin 1953 `juin 1954 rédigé par le secrétariat de la Commission sous la direction de M. le Dr F. Zehender, Zurich et accepté par la Commission des délégués lors de la réunion du 14 au 17 septembre 1955 `Strasbourg

Bericht der Experten-Kommission über die physikalisch-chemische Untersuchung des Rheinwassers / Rapport de la commission des experts sur les analyses physico-chimiques de l’eau du Rhin: 1. Serie Juni 1953 bis Juni 1954 ausgearbeitet vom Sekretariat der Kommission unter der Leitung von Herrn Dr. F. Zehender, Zürich, und von der Kommission der Delegierten genehmigt in der Sitzung vom 14. bis 17. September 1955 in Strassburg / lère série juin 1953 `juin 1954 rédigé par le secrétariat de la Commission sous la direction de M. le Dr F. Zehender, Zurich et accepté par la Commission des délégués lors de la réunion du 14 au 17 septembre 1955 `Strasbourg

1956 · PDF