Cover Image

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cervenjak, Philip, Gan, Junhao, Kakimura, Naonori, Umboh, Seeun William, Wirth, Anthony
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
by: Cervenjak, Philip, et al.
Published: (2024)

Fast Parallel Algorithms for Submodular $p$-Superseparable Maximization
by: Cervenjak, Philip, et al.
Published: (2023)

Optimal Dynamic Parameterized Subset Sampling
by: Gan, Junhao, et al.
Published: (2024)

Parameterized Complexity of Submodular Minimization under Uncertainty
by: Kakimura, Naonori, et al.
Published: (2024)

Online Computation of String Net Frequency
by: Guo, Peaker, et al.
Published: (2024)

On Approximating the Weighted Region Problem in Square Tessellations
by: Kakimura, Naonori, et al.
Published: (2024)

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
by: Dinitz, Michael, et al.
Published: (2025)

Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General
by: Shmoys, David, et al.
Published: (2026)

Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them
by: Canonne, Clément L., et al.
Published: (2025)

Optimal bounds on a tree inference algorithm
by: Gardiner, Jack, et al.
Published: (2024)

Online TCP Acknowledgment under General Delays
by: Bhore, Sujoy, et al.
Published: (2026)

Reconfiguration of labeled matchings in triangular grid graphs
by: Kakimura, Naonori, et al.
Published: (2024)

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
by: Bartal, Yair, et al.
Published: (2024)

Computing Power Indices in Weighted Majority Games with Formal Power Series
by: Kakimura, Naonori, et al.
Published: (2025)

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
by: Ezra, Tomer, et al.
Published: (2024)

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection
by: Huang, Chien-Chung, et al.
Published: (2026)

Colorful Vertex Recoloring of Bipartite Graphs
by: Patt-Shamir, Boaz, et al.
Published: (2025)

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
by: Ito, Takehiro, et al.
Published: (2025)

Improved Algorithms for Fair Matroid Submodular Maximization
by: Mahabadi, Sepideh, et al.
Published: (2026)

Maximization of Approximately Submodular Functions
by: Horel, Thibaut, et al.
Published: (2024)

A Threshold Greedy Algorithm for Noisy Submodular Maximization
by: Chen, Wenjing, et al.
Published: (2023)

$O(1)$-Round MPC Algorithms for Multi-dimensional Grid Graph Connectivity, EMST and DBSCAN
by: Gan, Junhao, et al.
Published: (2025)

Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints
by: Zhu, Yanhui, et al.
Published: (2024)

Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
by: Wan, Zongqi, et al.
Published: (2024)

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
by: Chen, Yixin, et al.
Published: (2025)

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
by: Spaeh, Fabian, et al.
Published: (2025)

Scalable Fair Influence Blocking Maximization via Approximately Monotonic Submodular Optimization
by: Fang, Qiangpeng, et al.
Published: (2026)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
by: Buchbinder, Niv, et al.
Published: (2025)

A Poisson Process for Submodular Maximization
by: Rozenman, Amit Ganz, et al.
Published: (2026)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
by: Buchbinder, Niv, et al.
Published: (2026)

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

Submodular Maximization in Exactly $n$ Queries
by: Balkanski, Eric, et al.
Published: (2024)

Learning-Augmented Dynamic Submodular Maximization
by: Agarwal, Arpit, et al.
Published: (2023)

Regularized Unconstrained Weakly Submodular Maximization
by: Zhu, Yanhui, et al.
Published: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
by: Chitnis, Rajesh, et al.
Published: (2024)

Practical Parallel Algorithms for Non-Monotone Submodular Maximization
by: Cui, Shuang, et al.
Published: (2023)

An Approximation Algorithm for Monotone Submodular Cost Allocation
by: Mizutani, Ryuhei
Published: (2025)

Consistent Submodular Maximization
by: Dütting, Paul, et al.
Published: (2024)

A Tight Competitive Ratio for Online Submodular Welfare Maximization
by: Ganz, Amit, et al.
Published: (2023)

Simultaneous Network Design with Restricted Link Usage
by: Kakimura, Naonori, et al.
Published: (2025)