東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Exploiting structure in combinatoria...

Dilkina, Bistra.

Linked to FindBook

Google Book

Amazon

博客來

Exploiting structure in combinatorial problems with applications in computational sustainability.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Exploiting structure in combinatorial problems with applications in computational sustainability./
Author:	Dilkina, Bistra.
Description:	214 p.
Notes:	Source: Dissertation Abstracts International, Volume: 73-09(E), Section: B.
Contained By:	Dissertation Abstracts International73-09B(E).
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3506777
ISBN:	9781267299239

Exploiting structure in combinatorial problems with applications in computational sustainability.
Dilkina, Bistra.

Exploiting structure in combinatorial problems with applications in computational sustainability. - 214 p.

Source: Dissertation Abstracts International, Volume: 73-09(E), Section: B.

Thesis (Ph.D.)--Cornell University, 2011.

Combinatorial decision and optimization problems are at the core of many tasks with practical importance in areas as diverse as planning and scheduling, supply chain management, hardware and software verification, electronic commerce, and computational biology. Another important source of combinatorial problems is the newly emerging field of computational sustainability, which addresses decision-making aimed at balancing social, economic and environmental needs to guarantee the long-term prosperity of life on our planet.

ISBN: 9781267299239Subjects--Topical Terms:

626642
Computer Science.

Exploiting structure in combinatorial problems with applications in computational sustainability.
LDR:03004nam 2200301 4500 001 1958075
005 20140224122710.5
008 150212s2011 ||||||||||||||||| ||eng d
020 $a 9781267299239
035 $a (MiAaPQ)AAI3506777
035 $a AAI3506777
040 $a MiAaPQ $c MiAaPQ
100 1 $a Dilkina, Bistra. $3 2093051
245 1 0 $a Exploiting structure in combinatorial problems with applications in computational sustainability.
300 $a 214 p.
500 $a Source: Dissertation Abstracts International, Volume: 73-09(E), Section: B.
500 $a Adviser: Carla Gomes.
502 $a Thesis (Ph.D.)--Cornell University, 2011.
520 $a Combinatorial decision and optimization problems are at the core of many tasks with practical importance in areas as diverse as planning and scheduling, supply chain management, hardware and software verification, electronic commerce, and computational biology. Another important source of combinatorial problems is the newly emerging field of computational sustainability, which addresses decision-making aimed at balancing social, economic and environmental needs to guarantee the long-term prosperity of life on our planet.
520 $a This dissertation studies different forms of problem structure that can be exploited in developing scalable algorithmic techniques capable of addressing large real-world combinatorial problems. There are three major contributions in this work: (1) We study a form of hidden problem structure called a backdoor, a set of key decision variables that captures the combinatorics of the problem, and reveal that many real-world problems encoded as Boolean satisfiability or mixed-integer linear programs contain small backdoors. We study backdoors both theoretically and empirically and characterize important tradeoffs between the computational complexity of finding backdoors and their effectiveness in capturing problem structure succinctly. (2) We contribute several domain-specific mathematical formulations and algorithmic techniques that exploit specific aspects of problem structure arising in budget-constrained conservation planning for wildlife habitat connectivity. Our solution approaches scale to real-world conservation settings and provide important decision-support tools for cost--benefit analysis. (3) We propose a new survey-planning methodology to assist in the construction of accurate predictive models, which are especially relevant in sustainability areas such as species-distribution prediction and climate-change impact studies. In particular, we design a technique that takes advantage of submodularity, a structural property of the function to be optimized, and results in a polynomial-time procedure with approximation guarantees.
590 $a School code: 0058.
650 4 $a Computer Science. $3 626642
650 4 $a Agriculture, Wood Technology. $3 1031154
650 4 $a Agriculture, Wildlife Conservation. $3 1672517
690 $a 0984
690 $a 0746
690 $a 0284
710 2 $a Cornell University. $3 530586
773 0 $t Dissertation Abstracts International $g 73-09B(E).
790 $a 0058
791 $a Ph.D.
792 $a 2011
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3506777