Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity (Q6142066): Difference between revisions

Latest revision as of 20:51, 23 August 2024

scientific article; zbMATH DE number 7794712

Language	Label	Description	Also known as
English	Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity	scientific article; zbMATH DE number 7794712

Statements

instance of

scholarly article

0 references

title

Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity (English)

0 references

0 references

0 references

0 references

0 references

Journal of Optimization Theory and Applications

0 references

publication date

25 January 2024

0 references

zbMATH Keywords

DR-submodular maximization

0 references

cardinality constraint

0 references

design and analysis of approximation algorithms

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s10957-023-02353-7

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

An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model

0 references

The adaptive complexity of maximizing a submodular function

0 references

Parallel algorithms for select and partition with noisy comparisons

0 references

Submodular Function Maximization in Parallel via the Multilinear Relaxation

0 references

Settling the Query Complexity of Non-adaptive Junta Testing

0 references

Q3549682

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

Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity

0 references

Maximizing Non-monotone Submodular Functions

0 references

A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice

0 references

On the Power of Adaptivity in Sparse Recovery

0 references

Online submodular welfare maximization: Greedy is optimal

0 references

Q2941641

0 references

Optimal Value of Information in Graphical Models

0 references

Q3096108

0 references

Q4149262

0 references

Best Algorithms for Approximating the Maximum of a Submodular Set Function

0 references

An analysis of approximations for maximizing submodular set functions—I

0 references

Rounds in Communication Complexity Revisited

0 references

Maximizing monotone submodular functions over the integer lattice

0 references

A note on maximizing a submodular set function subject to a knapsack constraint

0 references

Identifiers

DOI

10.1007/s10957-023-02353-7

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6142066

@@ 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 @@
+An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
+Normal rank
@@ Property / cites work @@
+The adaptive complexity of maximizing a submodular function
+Normal rank
@@ Property / cites work @@
+Parallel algorithms for select and partition with noisy comparisons
+Normal rank
@@ Property / cites work @@
+Submodular Function Maximization in Parallel via the Multilinear Relaxation
+Normal rank
@@ Property / cites work @@
+Settling the Query Complexity of Non-adaptive Junta Testing
+Normal rank
@@ Property / cites work @@
+Q3549682
@@ Property / cites work: Q3549682 / rank @@
+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 @@
+Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
+Normal rank
@@ Property / cites work @@
+Maximizing Non-monotone Submodular Functions
@@ Property / cites work: Maximizing Non-monotone Submodular Functions / rank @@
+Normal rank
@@ Property / cites work @@
+A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
+Normal rank
@@ Property / cites work @@
+On the Power of Adaptivity in Sparse Recovery
@@ Property / cites work: On the Power of Adaptivity in Sparse Recovery / rank @@
+Normal rank
@@ Property / cites work @@
+Online submodular welfare maximization: Greedy is optimal
+Normal rank
@@ Property / cites work @@
+Q2941641
@@ Property / cites work: Q2941641 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Value of Information in Graphical Models
@@ Property / cites work: Optimal Value of Information in Graphical Models / rank @@
+Normal rank
@@ Property / cites work @@
+Q3096108
@@ Property / cites work: Q3096108 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4149262
@@ Property / cites work: Q4149262 / rank @@
+Normal rank
@@ Property / cites work @@
+Best Algorithms for Approximating the Maximum of a Submodular Set Function
+Normal rank
@@ Property / cites work @@
+An analysis of approximations for maximizing submodular set functions—I
+Normal rank
@@ Property / cites work @@
+Rounds in Communication Complexity Revisited
@@ Property / cites work: Rounds in Communication Complexity Revisited / rank @@
+Normal rank
@@ Property / cites work @@
+Maximizing monotone submodular functions over the integer lattice
+Normal rank
@@ Property / cites work @@
+A note on maximizing a submodular set function subject to a knapsack constraint
+Normal rank