Copertina

Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Kuhnle, Alan
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
di: Chen, Yixin, et al.
Pubblicazione: (2020)

Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
di: Nath, Ankur, et al.
Pubblicazione: (2024)

Monotone Submodular Multiway Partition
di: Bi, Richard, et al.
Pubblicazione: (2024)

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

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

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
di: Chen, Yixin, et al.
Pubblicazione: (2026)

Deletion Robust Non-Monotone Submodular Maximization over Matroids
di: Dütting, Paul, et al.
Pubblicazione: (2022)

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

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
di: Kosolobov, Dmitry
Pubblicazione: (2024)

An Approximation Algorithm for Monotone Submodular Cost Allocation
di: Mizutani, Ryuhei
Pubblicazione: (2025)

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
di: Amanatidis, Georgios, et al.
Pubblicazione: (2020)

Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel
di: Chen, Yixin, et al.
Pubblicazione: (2021)

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

ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
di: Gallart, Joan Vendrell, et al.
Pubblicazione: (2025)

Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization
di: Chen, Yixin, et al.
Pubblicazione: (2024)

Online Monotone Metric Embeddings
di: Coester, Christian, et al.
Pubblicazione: (2026)

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

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
di: Khanna, Sanjeev, et al.
Pubblicazione: (2024)

Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models
di: Chen, Yixin, et al.
Pubblicazione: (2022)

Testing Monotonicity of Real-Valued Functions on DAGs
di: Yoshida, Yuichi
Pubblicazione: (2026)

Deterministic Monotone Min-Plus Product and Convolution
di: Jin, Ce, et al.
Pubblicazione: (2026)

Exploring Monotone Priority Queues for Dijkstra Optimization
di: Costa, Jonas, et al.
Pubblicazione: (2024)

$\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions
di: Bérczi, Kristóf, et al.
Pubblicazione: (2025)

Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
di: Pinto Jr, Renato Ferreira
Pubblicazione: (2024)

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
di: Dürr, Anita
Pubblicazione: (2022)

Non-Monotonicity in Fair Division of Graphs
di: Hosseini, Hadi, et al.
Pubblicazione: (2025)

Learning with Monotone Adversarial Corruptions
di: Larsen, Kasper Green, et al.
Pubblicazione: (2026)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
di: Kaul, Matthias, et al.
Pubblicazione: (2025)

On Exact Learning of $d$-Monotone Functions
di: Bshouty, Nader H.
Pubblicazione: (2025)

A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling
di: Jansen, Klaus, et al.
Pubblicazione: (2026)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
di: Black, Hadley
Pubblicazione: (2023)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
di: Bringmann, Karl, et al.
Pubblicazione: (2024)

A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
di: Beines, Arne, et al.
Pubblicazione: (2024)

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
di: Kobayashi, Yasuaki, et al.
Pubblicazione: (2020)

Semi-Bandit Learning for Monotone Stochastic Optimization
di: Agarwal, Arpit, et al.
Pubblicazione: (2023)

Retroactive Monotonic Priority Queues via Range Searching
di: Castro, Lucas, et al.
Pubblicazione: (2025)

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
di: Zhu, Yanhui, et al.
Pubblicazione: (2024)

A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
di: Black, Hadley, et al.
Pubblicazione: (2023)

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

Bicriteria Submodular Maximization
di: Feldman, Moran, et al.
Pubblicazione: (2025)