Kontraktionsbaseret adskillelse og løft til løsning af Max-Cut-problemet
- ophavsmand: Bonato, Dr. Thorsten
- Verfügbarkeit: Auf Lager
- EAN: 9783941274860
€49,90
Max-cut-problemet er et NP-hårdt kombinatorisk optimeringsproblem defineret på urettede vægtede grafer. Det består i at finde en delmængde af grafens noder, således at den samlede vægt af kanterne mellem delmængden og dens komplement maksimeres. Denne bog omhandler en ny separationstilgang, der skal bruges inden for en branch-and-cut-algoritme til at løse...
Max-cut-problemet er et NP-hårdt kombinatorisk optimeringsproblem defineret på urettede vægtede grafer. Det består i at finde en delmængde af grafens noder, således at den samlede vægt af kanterne mellem delmængden og dens komplement maksimeres. Denne bog omhandler en ny separationstilgang, der skal bruges inden for en branch-and-cut-algoritme til at løse max-cut-problemer til optimalitet. Metoden er baseret på grafsammentrækning og muliggør hurtig adskillelse af såkaldte ulige cyklusuligheder. Derudover beskriver vi teknikker til at tilføje muligvis manglende kanter til en allerede sammentrukket graf. Dette gør det muligt at løse max-cut problemer på sparsomme grafer ved hjælp af metoder, der oprindeligt var beregnet til komplette grafer og ikke kunne have været anvendt på anden måde. Vi undersøger de teoretiske aspekter af denne kombinerede tilgang og forklarer også dens realisering inden for en branch-and-cut-ramme. Til sidst evaluerer vi ydeevnen af vores separationsprocedure på en række forskellige testinstanser.
Detaljer
- Titel: Kontraktionsbaseret adskillelse og løft til løsning af Max-Cut-problemet
- Forfatter: Dr. Thorsten Bonato
- Udgave: 1. udgave
- Udgivet: 1. udgave 18.11.2011
- Afdeling: Matematik
- Produkttype: Bog (hardcover)
- Produkttype: Afhandling
- Sprog: Engelsk
- Indbinding: Softcover (paperback)
- Mål: 21,0 x 14,8 cm (DIN A5)
- Omfang: 197 sider
- Tilstand: Ny (krympeindpakket i folie)
- Søgeord: kunstig forlængelse, gren-og-skæring, kombinatorisk optimering, skåret polytop, grafkontraktion, løft, max-cut-problem, ulighed i ulige cyklus, polyhedral kombinatorik, projektion, separation, målsnit, ubegrænset kvadratisk 0-1 optimering
Downloads
DRM: Digitalt vandmærke
Denne e-bog indeholder et digitalt vandmærke og er derfor personliggjort til dig. Hvis e-bogen videregives til tredjeparter på misbrug, er det muligt at spore den tilbage til kilden.
Filformat: PDF (Portable Document Format)
Med et fast sidelayout er PDF'en særdeles velegnet til fagbøger med spalter, tabeller og figurer. En PDF kan vises på næsten alle enheder, men er kun egnet i begrænset omfang til små skærme (smartphone, e-reader).
Systemkrav:
PC/Mac: Du kan læse denne e-bog med en pc eller Mac. Du skal bruge en PDF-fremviser - fx Adobe Reader.
e-læser: Denne e-bog kan læses med (næsten) alle e-bogslæsere. Den er dog ikke kompatibel med Amazon Kindle.
Smartphone/tablet: Uanset om det er Apple eller Android, kan du læse denne e-bog. Du skal bruge en PDF-fremviser - fx Adobe Reader.
Køb af e-bøger fra udlandet
Af skatteretlige årsager kan vi sælge e-bøger kun inden for Tyskland og Schweiz. Vi kan desværre ikke opfylde e-bogsordrer fra andre lande.