國立虎尾科技大學 |

Hardness from Densest Subgraph Conjectures.

紀錄類型:	書目-語言資料,手稿 : Monograph/item
正題名/作者:	Hardness from Densest Subgraph Conjectures./
作者:	Naamad, Yonatan.
面頁冊數:	1 online resource (124 pages)
附註:	Source: Dissertation Abstracts International, Volume: 79-05(E), Section: B.
Contained By:	Dissertation Abstracts International79-05B(E).
標題:	Computer science. -
電子資源:	click for full text (PQDT)
ISBN:	9780355480702

Hardness from Densest Subgraph Conjectures.
Naamad, Yonatan.

Hardness from Densest Subgraph Conjectures. - 1 online resource (124 pages)

Source: Dissertation Abstracts International, Volume: 79-05(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

Karp's seminal paper on NP-Completeness provided computer scientists with a toolkit for showing computational hardness, conditioned on a complexity theoretic conjecture, for a wide variety of optimization problems. However, the techniques used in his paper say little about the hardness of approximating the optimal objective values of these problems. While researchers have since managed to find tight bounds on the approximability of some of these NP-hard problems, many others still have embarrassingly large gaps between their known upper and lower limits of approximation.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355480702Subjects--Topical Terms:

573171
Computer science.
Index Terms--Genre/Form:

554714
Electronic books.

Hardness from Densest Subgraph Conjectures.
LDR:03510ntm a2200361Ki 4500 001 909188
005 20180419121557.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355480702
035 $a (MiAaPQ)AAI10640013
035 $a (MiAaPQ)princeton:12377
035 $a AAI10640013
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Naamad, Yonatan. $3 1179811
245 1 0 $a Hardness from Densest Subgraph Conjectures.
264 0 $c 2017
300 $a 1 online resource (124 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 79-05(E), Section: B.
500 $a Adviser: Moses S. Charikar.
502 $a Thesis (Ph.D.) $c Princeton University $d 2017.
504 $a Includes bibliographical references
520 $a Karp's seminal paper on NP-Completeness provided computer scientists with a toolkit for showing computational hardness, conditioned on a complexity theoretic conjecture, for a wide variety of optimization problems. However, the techniques used in his paper say little about the hardness of approximating the optimal objective values of these problems. While researchers have since managed to find tight bounds on the approximability of some of these NP-hard problems, many others still have embarrassingly large gaps between their known upper and lower limits of approximation.
520 $a To fill in these gaps, researchers have posed myriad new complexity theoretic conjectures that entail stronger lower bounds at the expense of more demanding hypotheticals. One class of conjectures focuses on the approximability of the Densest k-Subgraph (DkS) problem. Namely, the conjectured hardness of both adversarial and average-case variants of DkS has been shown to imply stronger hardness for many problems for which good approximation algorithms have proven elusive.
520 $a In this dissertation, we study a variety of problems, each of which can have their hardness tied back to that of DkS. We describe techniques for proving stronger hardness results conditioned on both the known and the conjectured hardness of DkS. We show how previous results on DkS imply stronger lower bounds on "MinRep-hard" problems, as well as a simple technique for converting many proofs of MinRep-hardness into proofs of DkS-hardness. Using this and other techniques, we show DkS hardness for problems such as Target Set Selection, Minimum Monotone Satisfying Assignment, Min-Cost Colored Cut, Network Flow Interdiction, and Densest k-Common Subgraph, among others. In the case of Target Set Selection and Monotone Minimum Satisfying Assignment, we show how to obtain substantially stronger lower bounds by exploiting the self-similar structure of instances conjectured to be average-case-hard. We introduce the Middlebox Routing-class of problems, and show exact, approximation, and hardness results for its member problems. We provide an O(√n) approximation algorithm for Min k-Union, and discuss both approximation and hardness results for Densest Common Subgraph variants.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a Princeton University. $b Computer Science. $3 1179801
773 0 $t Dissertation Abstracts International $g 79-05B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10640013 $z click for full text (PQDT)