Capa do livro de Zur Komplexität der Reduzierbarkeit von Open-Shop-Plänen
Título do livro:

Zur Komplexität der Reduzierbarkeit von Open-Shop-Plänen

Erkennung effizienter Pläne: Beschreibung mittels H-Comparabilitygraphen und Analyse der Zeitkomplexität

Südwestdeutscher Verlag für Hochschulschriften (2010-09-05 )

Books loader

Omni badge Apto para vale
ISBN- 1 3:

978-3-8381-1798-0

ISBN- 1 0:
3838117980
EAN:
9783838117980
Idioma do livro:
Alemão
Anotações e citações/ texto breve:
Das Open-Shop Schedulingproblem liegt in der Komplexitätsklasse NP-complete. Ein möglicher Weg zur Entwicklung von neuen Heuristiken zur Lösung von Open-Shop Problemen ist die Einschränkung des Suchraums auf effiziente Lösungen. Aus diesem Ansatz entwickelte sich die Theorie der Reduzierbarkeit von Open-Shop Plänen. Ein Plan heißt irreduzibel, wenn es keinen anderen Plan gibt, der bei beliebiger Wahl der Bearbeitungszeiten einen besseren Zielfunktionswert liefert. In dieser Arbeit wird die Komplexität des Reduzierbarkeitsproblems (REDUCIBILITY) untersucht. Bekannt ist die Zugehörigkeit von REDUCIBILITY zu NP. Untersucht werden die Bedingungen, unter denen das komplementäre Problem IRREDUCIBILITY in NP, und damit in NP ∩ co-NP = ZPP*, oder sogar in P liegt. Es wird ein Algorithmus vorgestellt, der reduzierbare Pläne nichtdeterministisch reduziert, und irreduzible Pläne nur unter sehr engen Voraussetzungen nicht als irreduzibel erkennen kann. Die Hinweise auf die Zugehörigkeit von IRREDUCIBILITY zu P oder zu NP- incomplete = NP − (P + NP-complete) werden diskutiert.
Editora:
Südwestdeutscher Verlag für Hochschulschriften
Website:
https://www.svh-verlag.de
Por (autor):
Michael Andresen
Número de páginas:
304
Publicado em:
2010-09-05
Stock:
Disponível
Categoria:
Matemática
Preço:
89.9 €
Palavras chave:
irreduzible Pläne, H-Comparabilitygraphen, Open-Shop, Komplexität, ZPP*, NP-incomplete

Books loader

Boletim informativo

Adyen::amex Adyen::mc Adyen::visa Adyen::cup Adyen::unionpay PayPal Transferência Bancária

  0 produtos no carrinho
Editar carrinho
Loading frontend
LOADING