東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Linked to FindBook

Google Book

Amazon

博客來

Submodular Optimization in Massive Datasets.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Submodular Optimization in Massive Datasets./
Author:	Liu, Paul.
Description:	1 online resource (115 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 84-04, Section: B.
Contained By:	Dissertations Abstracts International84-04B.
Subject:	Paradigms. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=29342237click for full text (PQDT)
ISBN:	9798352604526

Submodular Optimization in Massive Datasets.
Liu, Paul.

Submodular Optimization in Massive Datasets. - 1 online resource (115 pages)

Source: Dissertations Abstracts International, Volume: 84-04, Section: B.

Thesis (Ph.D.)--Stanford University, 2022.

Includes bibliographical references

In this thesis, we study the problem of submodular maximization in various "massive data" models, namely the MapReduce, streaming, and adaptive models.For the MapReduce model, we give a simple O(1/ε)-round algorithm for maximizing a monotone submodular function with respect to a cardinality constraint. This algorithm achieves an optimal 1 − 1/e approximation ratio, is simple to implement in practice, and removes the data duplication issue of prior works obtaining the same approximation ratio.For the streaming model, we study both the random order and the adversarial order settings. In both settings, we give the first multi-pass approximation algorithm for maximizing monotone submodular functions with respect to a matroid constraint. Our algorithms achieve 1 − 1/e − ε approximations in poly(1/ε) passes. For the adversarial case, it is known that our algorithm is tight - it is impossible to achieve better than a 1/2 approximation in a single pass, and anything better than 1 − 1/e requires linearly many passes. Our techniques also allows us to develop single pass and multi-pass algorithms for the p-matchoid constraint, which generalizes the popular matroid (p = 1) and intersection-of-matroids constraint (p = 2). In the adaptive model, we study the problem of maximizing an unconstrained nonmonotone submodular function. We show the following: for any problem instance, and every δ > 0, either we obtain a (1/2 − δ)-approximation in 1 round, or a (1/2 + Ω(δ 2))- approximation in Ω(1/δ2) rounds. In particular (and in contrast to known lower bounds for the monotone cardinality constrained case), there cannot be an instance where (i) it is impossible to achieve an approximation factor better than 1/2 regardless of the number of rounds, and (ii) it takes r rounds to achieve a factor of 1/2 − O(1/r).

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

Mode of access: World Wide Web

ISBN: 9798352604526Subjects--Topical Terms:

3560141
Paradigms.
Index Terms--Genre/Form:

542853
Electronic books.

Submodular Optimization in Massive Datasets.
LDR:03068nmm a2200337K 4500 001 2364235
005 20231130104206.5
006 m o d
007 cr mn ---uuuuu
008 241011s2022 xx obm 000 0 eng d
020 $a 9798352604526
035 $a (MiAaPQ)AAI29342237
035 $a (MiAaPQ)STANFORDvw164nb4193
035 $a AAI29342237
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Liu, Paul. $3 3705040
245 1 0 $a Submodular Optimization in Massive Datasets.
264 0 $c 2022
300 $a 1 online resource (115 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: Dissertations Abstracts International, Volume: 84-04, Section: B.
500 $a Advisor: Vondrak, Jan;Rubinstein, Aviad;Charikar, Moses.
502 $a Thesis (Ph.D.)--Stanford University, 2022.
504 $a Includes bibliographical references
520 $a In this thesis, we study the problem of submodular maximization in various "massive data" models, namely the MapReduce, streaming, and adaptive models.For the MapReduce model, we give a simple O(1/ε)-round algorithm for maximizing a monotone submodular function with respect to a cardinality constraint. This algorithm achieves an optimal 1 − 1/e approximation ratio, is simple to implement in practice, and removes the data duplication issue of prior works obtaining the same approximation ratio.For the streaming model, we study both the random order and the adversarial order settings. In both settings, we give the first multi-pass approximation algorithm for maximizing monotone submodular functions with respect to a matroid constraint. Our algorithms achieve 1 − 1/e − ε approximations in poly(1/ε) passes. For the adversarial case, it is known that our algorithm is tight - it is impossible to achieve better than a 1/2 approximation in a single pass, and anything better than 1 − 1/e requires linearly many passes. Our techniques also allows us to develop single pass and multi-pass algorithms for the p-matchoid constraint, which generalizes the popular matroid (p = 1) and intersection-of-matroids constraint (p = 2). In the adaptive model, we study the problem of maximizing an unconstrained nonmonotone submodular function. We show the following: for any problem instance, and every δ > 0, either we obtain a (1/2 − δ)-approximation in 1 round, or a (1/2 + Ω(δ 2))- approximation in Ω(1/δ2) rounds. In particular (and in contrast to known lower bounds for the monotone cardinality constrained case), there cannot be an instance where (i) it is impossible to achieve an approximation factor better than 1/2 regardless of the number of rounds, and (ii) it takes r rounds to achieve a factor of 1/2 − O(1/r).
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2023
538 $a Mode of access: World Wide Web
650 4 $a Paradigms. $3 3560141
650 4 $a Algorithms. $3 536374
650 4 $a Communication. $3 524709
650 4 $a Optimization. $3 891104
650 4 $a Computer science. $3 523869
655 7 $a Electronic books. $2 lcsh $3 542853
690 $a 0459
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 783688
710 2 $a Stanford University. $3 754827
773 0 $t Dissertations Abstracts International $g 84-04B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=29342237 $z click for full text (PQDT)