近似算法是處理難解的組合優(yōu)化問(wèn)題的一個(gè)非常重要和有效的方法。它可以在多項(xiàng)式時(shí)間內(nèi)求得問(wèn)題的一個(gè)解，并使其目標(biāo)函數(shù)值與解的目標(biāo)函數(shù)值之比不超過(guò)一個(gè)常數(shù)。本書(shū)將通過(guò)大量具有代表性的組合優(yōu)化問(wèn)題，介紹近似算法設(shè)計(jì)和分析中的三種主要方法：貪婪算法、限制方法和松弛方法；所討論的問(wèn)題來(lái)源于不同的研究和應(yīng)用領(lǐng)域，其中包括通信網(wǎng)絡(luò)設(shè)計(jì)，光纖網(wǎng)絡(luò)，無(wú)線自組織網(wǎng)絡(luò)和傳感器網(wǎng)絡(luò)，生物信息學(xué)，社會(huì)網(wǎng)絡(luò)，工業(yè)工程和信息管理系統(tǒng)等。此外，本書(shū)還將介紹有關(guān)組合優(yōu)化問(wèn)題不可近似性的一些基本結(jié)果。本書(shū)的每一章后面都配有相關(guān)內(nèi)容的習(xí)題和歷史注記。
《近似算法的設(shè)計(jì)與分析》可作為計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)專(zhuān)業(yè)高年級(jí)本科生和研究生的近似算法課程的教材，亦可作為相關(guān)研究領(lǐng)域科研人員的參考書(shū)。
近似算法是處理難解的組合優(yōu)化問(wèn)題的一個(gè)非常重要和有效的方法。它可以在多項(xiàng)式時(shí)間內(nèi)求得問(wèn)題的一個(gè)解，并使其目標(biāo)函數(shù)值與解的目標(biāo)函數(shù)值之比不超過(guò)一個(gè)常數(shù)。
堵丁柱，1948年生。中國(guó)科學(xué)院應(yīng)用數(shù)學(xué)研究所運(yùn)籌學(xué)碩士(1981)，美國(guó)加利福尼亞大學(xué)圣巴巴拉分校數(shù)學(xué)博士(1985)，美國(guó)伯克利數(shù)學(xué)科學(xué)研究所博士后(1985－1986)，美國(guó)麻省理工學(xué)院助理教授(1986－1987)，美國(guó)普林斯頓大學(xué)訪問(wèn)學(xué)者(1990－1991)。曾任美國(guó)明尼蘇達(dá)大學(xué)計(jì)算機(jī)科學(xué)系教授，中國(guó)科學(xué)院應(yīng)用數(shù)學(xué)研究所研究員，美國(guó)自然科學(xué)基金會(huì)項(xiàng)目主任，西安交通大學(xué)理學(xué)院院長(zhǎng)。現(xiàn)任美國(guó)得克薩斯大學(xué)達(dá)拉斯分校計(jì)算機(jī)系教授，西安交通大學(xué)理學(xué)院名譽(yù)院長(zhǎng)和高麗大學(xué)大學(xué)教授。
