Recently, Udwani defined a new class of set functions under monotonicity and subadditivity, called submodular order functions, which is a subfamily of submodular functions. Informally, the submodular order function admits a very limited form of submodularity which is defined over a specific permutation of the ground set. His work pointed out the intriguing connection between streaming submodular maximization and submodular order maximization. Inspired by a 0.25-approximation streaming algorithm for maximizing a monotone submodular function subject to a matroid constraint, Udwani gave a 0.25-approximation algorithm for submodular order functions maximization subject to a matroid constraint. Based on the above results, we would like to explore further in which cases it is feasible to generalize from streaming submodular maximization algorithms to submodular order maximization algorithms. As a more general constraint than matroid, p-matchoid is a collection of p matroids with each matroid defined on some subsets of the ground set. Related work gave a 1/4p-approximation streaming algorithm for monotone submodular functions maximization under a p-matchoid constraint. Inspired by the above algorithms and the intriguing connection, we used some techniques to try to generalize several streaming algorithms for submodular functions to the offline algorithms for submodular order functions, including interleaved partitions and incremental values. Assuming that the objective function f is subadditive and non-negative, we gave a 1/4p-approximation algorithm for monotone submodular order maximization to a p-matchoid constraint. In addition, we summarize the failures of other cases. / Nyligen definierade Udwani en ny klass av mängdfunktioner under monotonicitet och subadditivitet, som kallas submodulära ordningsfunktioner och som är en underfamilj av submodulära funktioner. Informellt sett medger den submodulära ordningsfunktionen en mycket begränsad form av submodularitet som är definierad över en specifik permutation av grundmängden. Hans arbete pekade på det spännande sambandet mellan strömmande submodulär maximering och submodulär ordermaximering. Inspirerad av en strömningsalgoritm med 0.25-approximation för maximering av en monoton submodulär funktion som är föremål för en matroidbegränsning, gav Udwani en algoritm med 0.25-approximation för maximering av submodulära ordningsfunktioner som är föremål för en matroidbegränsning. Baserat på ovanstående resultat skulle vi vilja utforska ytterligare i vilka fall det är möjligt att generalisera från algoritmer för strömning av submodulära maximeringsfunktioner till algoritmer för maximering av submodulära orderfunktioner. Som en mer allmän begränsning än matroid är p-matchoid en samling av p matroider där varje matroid definieras på vissa delmängder av grundmängden. Relaterade arbeten gav en strömmingsalgoritm med 1/4p-tillnärmning för monoton submodulär funktionsmaximering under en p-matchoid-begränsning. Inspirerade av ovanstående algoritmer och det spännande sambandet använde vi vissa tekniker för att försöka generalisera flera strömningsalgoritmer för submodulära funktioner till offline-algoritmer för submodulära ordningsfunktioner, inklusive interleaved partitions och inkrementella värden. Under förutsättning att målfunktionen f är subadditiv och icke-negativ gav vi en algoritm för 1/4p-tillnärmning för monoton submodulär ordermaximering till ett p-matchoid-begränsningsvillkor. Dessutom sammanfattar vi misslyckanden i andra fall.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-320936 |
| Date | January 2022 |
| Creators | Wu, Yizhan |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2022:608 |
Page generated in 0.0025 seconds