Buch, Italienisch, 664 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 1036 g
Reihe: UNITEXT
Teoria e Algoritmi
Buch, Italienisch, 664 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 1036 g
Reihe: UNITEXT
ISBN: 978-88-470-1522-7
Verlag: Springer Milan
risultati teorici e gli algoritmi che, al contrario delle euristiche, hanno una garanzia
di avere buone prestazioni. Comprende una vasta scelta di argomenti e nasce
come riferimento di diversi corsi di ottimizzazione combinatoria sia di base che di
livello avanzato. Il libro contiene dimostrazioni complete (ma concise) anche
di molti risultati avanzati, alcuni dei quali non sono mai apparsi prima in un libro.
Vengono anche trattati molti dei temi di ricerca più attuali e sono riportati molti
riferimenti alla letteratura. Quindi questo libro, traduzione della quarta edizione in lingua originale, rappresenta lo stato dell’arte dell’ottimizzazione combinatoria.
Zielgruppe
Research
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
1 Introduzione. 3
1.1 Enumerazione. 4
1.2 Tempo di esecuzione degli algoritmi. 7
1.3 Problemi di ottimizzazione lineare. 11
1.4 Ordinamento. 12
Esercizi. 14
Riferimenti bibliografici. 15
2 Grafi. 17
2.1 Definizioni fondamentali. 17
2.2 Alberi, cicuiti, e tagli. 21
2.3 Connettività. 28
2.4 Grafi di Eulero e grafi bipartiti. 35
2.5 Planarità. 38
2.6 Dualità Planare. 45
Esercizi. 47
Riferimenti bibliografici. 51
3 Programmazione lineare. 55
3.1 Poliedri. 56
3.2 Algoritmo del simplesso. 60
3.3 Implementazione dell’algoritmo del simplesso. 63
3.4 Dualità. 66
3.5 Inviluppi convessi and politopi. 70
Esercizi. 72
Riferimenti bibliografici. 74
4 Algoritmi di programmazione lineare. 77
4.1 Dimensione dei vertici e delle facce. 77
4.2 Frazioni continue. 80
4.3 Eliminazione di Gauss. 83
4.4 Il metodo dell’elissoide. 86
4.5 Il Teorema di Khachiyan. 92
4.6 Separazione ed ottimizzazione. 94
Esercizi. 101
Riferimenti bibliografici. 102
5 Programmazione intera. 105
5.1 Inviluppo convesso di un poliedro. 107
5.2 Trasformazioni unimodulari. 111
5.3 Integralità totalmente duale. 113
5.4 Matrici totalmente unimodulari. 116
5.5 Piani di taglio. 121
5.6 Rilassamento lagrangiano. 125
Esercizi. 127
Riferimenti bibliografici. 131
6 Alberi di supporto e arborescenze. 135
6.1 Alberi di supporto minimo. 135
6.2 Arborescenze di peso minimo. 142
6.3 Descrizioni poliedrali. 146
6.4 Packing alberi di supporto e arborescenze. 149
Esercizi. 152
Riferimenti bibliografici. 156
7 Cammini minimi. 159
7.1 Cammini minimi da una singola sorgente. 160
7.2 Cammini minimi tra tutte le coppie di vertici. 164
7.3 Circuiti di peso medio minimo. 166
Esercizi. 169
Riferimenti bibliografici. 171
8 Reti di flusso. 173
8.1 Il Teorema di massimo flusso–minimo taglio. 174
8.2 Teorema di Menger. 178
8.3 Algoritmo di Edmonds-Karp. 180
8.4 Flussi bloccanti e il teorema di Fujishige. 182
8.5 L’algoritmo di Goldberg-Tarjan. 184
8.6 Alberi di Gomory-Hu. 188
8.7 Taglio di capacità minima in grafo non-orientato. 195
Esercizi. 197
Riferimenti bibliografici. 203
9 Flussi di costo minimo. 207
9.1 Formulazione del problema. 207
9.2 Un criterio di ottimalità. 209
9.3 Algoritmo di cancellazione di cicli di peso medio minimo. 211
9.4 Algoritmo di Ford-Fulkerson scmcfpath. 215
9.5 Algortimo di Orlin. 219
9.6 Algoritmo del simplesso per le reti di flusso scnetworksimplex. 223
9.7 Flussi temporali. 227
Esercizi. 229
Riferimenti bibliografici. 232
10 Accoppiamenti di peso massimo. 235
10.1 Accoppiamento bipartito. 236
10.2 La matrice di Tutte. 238
10.3 Il teorema di Tutte. 240
10.4 Ear-Decomposizione di grafi Factor-Critical. 243
10.5 Algoritmo di accopiamento di Edmonds. 249
Esercizi. 258
Riferimenti bibliografici. 262
11 Matching Pesato. 265
11.1 Il problema di assegnamento. 266
11.2 Schema dell’algoritmo di accoppiamento di peso massimo. 267
11.3 Implementazione dell’algoritmo di matching pesato massimo. 270
11.4 Postottimalità. 283
11.5 Il politopo di matching. 284
Esercizi. 287
Riferimenti bibliografici. 289
12 b-Matchings e T -Joins. 291
12.1 b-Accoppiamenti. 291
12.2 T -Joins di peso minimo. 295
12.3 T -Joins e T -Tagli. 299
12.4 Il teorema di Padberg-Rao. 303
Esercizi. 305
Riferimenti bibliografici. 307
13 Matroidi. 311
13.1 Sistemi di indipendenza e matroidi. 311
13.2 Altri assiomi sui matroidi. 315
13.3 Dualità. 319
13.4 L’algoritmo greedy. 323
13.5 Intersezione di matroidi. 328
13.6 Partizione di matroidi. 333
13.7 Intersezione di matroidi pesata. 335
Esercizi. 338
Riferimenti bibliografici. 340
14 Generalizzazioni di matroidi. 343
14.1 Greedoidi. 343
14.2 Polimatroidi. 347
14.3 Minimizzazione di funzioni submodulari. 351
14.4 Algoritmo di Schrijver. 353
14.5 Funzioni submodulari simmetriche. 357
Esercizi. 359
Riferimenti bibliografici. 362
15 NP-Completezza. 365
15.1 Macchine di Turing. 365
15.2 L’ipotesi di Church. 368
15.3 P e NP. 373
15.4 Il teorema di Cook. 377
15.5 Alcuni problemi NP-Completi fondamentali. 381
15.6 La classe coNP. 388
15.7 Problemi NP-Difficili. 390
Esercizi. 394
Riferimenti bibliografici. 398
16 Algoritmi approssimati. 401
16.1 Set Covering. 402
16.2 Il problema del taglio-massimo. 407
16.3 Colorazioni. 413
16.4 Schemi di approssimazione. 421
16.5 Soddisfacibilità massima. 423
16.6 Il teorema PCP. 428
16.7 L-Riduzioni. 432
Esercizi. 438
Riferimenti bibliografici. 442
17 Il problema dello zaino. 447
17.1 Zaino frazionario e il problema del mediano pesato. 447
17.2 Un algoritmo pseudopolinomiale. 450
17.3 Uno schema di approssimazione pienamente polinomiale. 452
Esercizi. 455
Riferimenti bibliografici. 456
18 Bin-Packing. 457
18.1 Euristiche Greedy. 457
18.2 Uno schema di approssimazione asintotico. 463
18.3 Algoritmo di Karmarkar-Karp. 467
Esercizi. 470
Riferimenti bibliografici. 472
19 Flussi multi-prodotto e cammini disgiunti per archi. 475
19.1 Flussi multi-prodotto. 476
19.2 Algoritmi per flussi multi-prodotto. 480
19.3 Il problema di cammini diretti disgiunti per archi. 484
19.4 Il problema di cammini non-diretti disgiunti per archi. 488
Esercizi. 494
Riferimenti bibliografici. 497
20 Problemi di progettazione di reti. 501
20.1 Alberi di Steiner. 502
20.2 L’algoritmo di Robins-Zelikovsky. 507
20.3 Progettazione di reti affidabili. 512
20.4 Un algoritmo di approssimazione primale-duale. 515
20.5 L’algoritmo di Jain. 524
Esercizi. 530
Riferimenti bibliografici. 533
21 Il problema del commesso viaggiatore. 537
21.1 Algoritmi di approssimazione. 537
21.2 Il problema del commesso viaggiatore euclideo. 542
21.3 Ricerca locale. 549
21.4 Il politopo del commesso viaggiatore. 555
21.5 Stime per difetto. 561
21.6 Branch-and-Bound. 563
Esercizi. 566
Riferimenti bibliografici. 569
22 Localizzazione di impianti. 573
22.1 Localizzazione di impianti senza limiti di capacit`a. 573
22.2 Arrotondamento di soluzioni di programmazione lineare. 575
22.3 Algoritmi primali-duali. 577
22.4 Scaling e Greedy Augmentation. 583
22.5 Stima sul numero di impianti. 586
22.6 Ricerca locale. 589
22.7 Localizzazione di impianti con limiti di capacità. 595
22.8 Localizzazione di impianti generale. 598
Esercizi. 604
Riferimenti bibliografici. 606
