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