Image de couverture de livre

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Chen, Yixin, Chen, Wenjing, Kuhnle, Alan
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
par: Chen, Yixin, et autres
Publié: (2020)

Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization
par: Chen, Yixin, et autres
Publié: (2024)

Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel
par: Chen, Yixin, et autres
Publié: (2021)

Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models
par: Chen, Yixin, et autres
Publié: (2022)

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
par: Chen, Yixin, et autres
Publié: (2026)

Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation
par: Kuhnle, Alan
Publié: (2026)

Submodular Maximization in Exactly $n$ Queries
par: Balkanski, Eric, et autres
Publié: (2024)

Bicriteria Algorithms for Submodular Cover with Partition and Fairness Constraints
par: Chen, Wenjing, et autres
Publié: (2026)

A Threshold Greedy Algorithm for Noisy Submodular Maximization
par: Chen, Wenjing, et autres
Publié: (2023)

ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
par: Gallart, Joan Vendrell, et autres
Publié: (2025)

Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
par: Pham, Canh V.
Publié: (2024)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
par: Chen, Shengminjie, et autres
Publié: (2026)

Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
par: Udwani, Rajan
Publié: (2024)

Linear Submodular Maximization with Bandit Feedback
par: Chen, Wenjing, et autres
Publié: (2024)

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
par: Cervenjak, Philip, et autres
Publié: (2026)

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
par: Amanatidis, Georgios, et autres
Publié: (2021)

Improved Algorithms for Fair Matroid Submodular Maximization
par: Mahabadi, Sepideh, et autres
Publié: (2026)

Maximization of Approximately Submodular Functions
par: Horel, Thibaut, et autres
Publié: (2024)

Practical Parallel Algorithms for Non-Monotone Submodular Maximization
par: Cui, Shuang, et autres
Publié: (2023)

Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints
par: Zhu, Yanhui, et autres
Publié: (2024)

Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
par: Wan, Zongqi, et autres
Publié: (2024)

Fast Parallel Algorithms for Submodular $p$-Superseparable Maximization
par: Cervenjak, Philip, et autres
Publié: (2023)

Bicriteria Submodular Maximization
par: Feldman, Moran, et autres
Publié: (2025)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
par: Shah, Vihan
Publié: (2026)

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
par: Spaeh, Fabian, et autres
Publié: (2025)

Scalable Fair Influence Blocking Maximization via Approximately Monotonic Submodular Optimization
par: Fang, Qiangpeng, et autres
Publié: (2026)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
par: Buchbinder, Niv, et autres
Publié: (2025)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
par: Buchbinder, Niv, et autres
Publié: (2026)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
par: Armbruster, Alexander, et autres
Publié: (2026)

Learning-Augmented Dynamic Submodular Maximization
par: Agarwal, Arpit, et autres
Publié: (2023)

A Poisson Process for Submodular Maximization
par: Rozenman, Amit Ganz, et autres
Publié: (2026)

Regularized Unconstrained Weakly Submodular Maximization
par: Zhu, Yanhui, et autres
Publié: (2024)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
par: Ferber, Asaf, et autres
Publié: (2025)

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
par: Amanatidis, Georgios, et autres
Publié: (2020)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
par: Bernstein, Aaron, et autres
Publié: (2025)

Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint
par: Rui, Xiaobin, et autres
Publié: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
par: Mahabadi, Sepideh, et autres
Publié: (2025)

Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
par: Nath, Ankur, et autres
Publié: (2024)

An Approximation Algorithm for Monotone Submodular Cost Allocation
par: Mizutani, Ryuhei
Publié: (2025)

Consistent Submodular Maximization
par: Dütting, Paul, et autres
Publié: (2024)