Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model (Q5028360): Difference between revisions

Latest revision as of 11:25, 30 July 2024

scientific article; zbMATH DE number 7471553

Language	Label	Description	Also known as
English	Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model	scientific article; zbMATH DE number 7471553

Statements

instance of

scholarly article

0 references

title

Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model (English)

0 references

0 references

0 references

0 references

0 references

SIAM Journal on Discrete Mathematics

0 references

publication date

9 February 2022

0 references

full work available at URL

https://arxiv.org/abs/2002.05477

0 references

zbMATH Keywords

submodular function maximization

0 references

streaming model

0 references

approximation algorithm

0 references

inapproximability

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Fast algorithms for maximizing submodular functions

0 references

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation

0 references

The adaptive complexity of maximizing a submodular function

0 references

Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

0 references

Submodular maximization meets streaming: matchings, matroids, and more

0 references

Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids

0 references

Online Submodular Maximization Problem with Vector Packing Constraint.

0 references

Streaming Algorithms for Submodular Function Maximization

0 references

Submodular Function Maximization in Parallel via the Multilinear Relaxation

0 references

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

0 references

A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint

0 references

Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time

0 references

Q5091209

0 references

A threshold of ln <i>n</i> for approximating set cover

0 references

The one-way communication complexity of submodular maximization with applications to streaming and robustness

0 references

Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search

0 references

An analysis of approximations for maximizing submodular set functions—I

0 references

Q4196269

0 references

Multi-pass streaming algorithms for monotone submodular function maximization

0 references

Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

0 references

Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

0 references

Q2941641

0 references

Q3096108

0 references

Q4633865

0 references

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

0 references

Better streaming algorithms for the maximum coverage problem

0 references

Best Algorithms for Approximating the Maximum of a Submodular Set Function

0 references

Combinatorial optimization. Polyhedra and efficiency (3 volumes)

0 references

Symmetry and Approximability of Submodular Maximization Problems

0 references

Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems

0 references

Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint

0 references

Identifiers

DOI

10.1137/20M1357317

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5028360

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Fast algorithms for maximizing submodular functions
+Normal rank
@@ Property / cites work @@
+An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
+Normal rank
@@ Property / cites work @@
+The adaptive complexity of maximizing a submodular function
+Normal rank
@@ Property / cites work @@
+Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
+Normal rank
@@ Property / cites work @@
+Submodular maximization meets streaming: matchings, matroids, and more
+Normal rank
@@ Property / cites work @@
+Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
+Normal rank
@@ Property / cites work @@
+Online Submodular Maximization Problem with Vector Packing Constraint.
+Normal rank
@@ Property / cites work @@
+Streaming Algorithms for Submodular Function Maximization
+Normal rank
@@ Property / cites work @@
+Submodular Function Maximization in Parallel via the Multilinear Relaxation
+Normal rank
@@ Property / cites work @@
+Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
+Normal rank
@@ Property / cites work @@
+A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
+Normal rank
@@ Property / cites work @@
+Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
+Normal rank
@@ Property / cites work @@
+Q5091209
@@ Property / cites work: Q5091209 / rank @@
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+The one-way communication complexity of submodular maximization with applications to streaming and robustness
+Normal rank
@@ Property / cites work @@
+Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
+Normal rank
@@ Property / cites work @@
+An analysis of approximations for maximizing submodular set functions—I
+Normal rank
@@ Property / cites work @@
+Q4196269
@@ Property / cites work: Q4196269 / rank @@
+Normal rank
@@ Property / cites work @@
+Multi-pass streaming algorithms for monotone submodular function maximization
+Normal rank
@@ Property / cites work @@
+Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
+Normal rank
@@ Property / cites work @@
+Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
+Normal rank
@@ Property / cites work @@
+Q2941641
@@ Property / cites work: Q2941641 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3096108
@@ Property / cites work: Q3096108 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4633865
@@ Property / cites work: Q4633865 / rank @@
+Normal rank
@@ Property / cites work @@
+Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
+Normal rank
@@ Property / cites work @@
+Better streaming algorithms for the maximum coverage problem
+Normal rank
@@ Property / cites work @@
+Best Algorithms for Approximating the Maximum of a Submodular Set Function
+Normal rank
@@ Property / cites work @@
+Combinatorial optimization. Polyhedra and efficiency (3 volumes)
+Normal rank
@@ Property / cites work @@
+Symmetry and Approximability of Submodular Maximization Problems
+Normal rank
@@ Property / cites work @@
+Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
+Normal rank
@@ Property / cites work @@
+Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
+Normal rank
@@ Property / OpenAlex ID @@
+W4297823791
@@ Property / OpenAlex ID: W4297823791 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:5028360