Cover Image

Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Yixin, Nath, Ankur, Peng, Chunli, Kuhnle, Alan
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Discrete Mathematics Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
by: Tukan, Murad, et al.
Published: (2024)

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

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

A Unified Approach to Submodular Maximization Under Noise
by: Bhawalkar, Kshipra, et al.
Published: (2025)

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

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

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

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
by: Klimm, Max, et al.
Published: (2022)

Difference of Submodular Minimization via DC Programming
by: Halabi, Marwa El, et al.
Published: (2023)

A 1/2-Approximation for Budgeted $k$-Submodular Maximization
by: Wang, Chenhao
Published: (2025)

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

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
by: Crane, Alex, et al.
Published: (2025)

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

An Exact Solver for Submodular Knapsack Problems
by: Münch, Sabine, et al.
Published: (2025)

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

An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
by: Xue, Jinghui, et al.
Published: (2024)

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
by: Veldt, Nate, et al.
Published: (2025)

Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations
by: He, Xi
Published: (2025)

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
by: Abboud, Amir, et al.
Published: (2025)

A Unified Approach to Minimizing Symmetric Submodular Functions
by: Iwata, Satoru, et al.
Published: (2026)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

Cuts and Gauges for Submodular Width
by: Lanzinger, Matthias
Published: (2026)

Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
by: Zhang, Bohang, et al.
Published: (2024)

On the Parameterized Intractability of Determinant Maximization
by: Ohsaka, Naoto
Published: (2022)

Partial Optimality in the Preordering Problem
by: Stein, David, et al.
Published: (2026)

Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms
by: Davies, Sami, et al.
Published: (2025)

Exact Causal Attention with 10% Fewer Operations
by: Rybin, Dmitry, et al.
Published: (2025)

Graph Inference with Effective Resistance Queries
by: Bennett, Huck, et al.
Published: (2025)

Worst-case Error Bounds for Online Learning of Smooth Functions
by: Xie, Weian
Published: (2025)

Breaking Hard Isomorphism Benchmarks with DRESS
by: Velilla, Eduar Castrillo
Published: (2026)

Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
by: Sharman, Bharat, et al.
Published: (2025)

Optimal hypersurface decision trees
by: He, Xi
Published: (2025)

A 4-approximation algorithm for min max correlation clustering
by: Heidrich, Holger, et al.
Published: (2023)

Grouping Strategies on Two-Phase Methods for Bi-objective Combinatorial Optimization
by: Mota, Felipe O., et al.
Published: (2025)

Proceedings of the 13th edition of the conference on Random Generation of Combinatorial Structures. Polyominoes and Tilings
by: Brlek, Srečko, et al.
Published: (2024)

Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
by: Brosse, Caroline, et al.
Published: (2024)

Are Graph Neural Networks Optimal Approximation Algorithms?
by: Yau, Morris, et al.
Published: (2023)