Cover Image

Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Tukan, Murad, Mualem, Loay, Feldman, Moran
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Discrete Mathematics Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

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

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
by: Veldt, Nate, 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)

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

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

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

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

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

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)

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
by: Crane, Alex, 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)

Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations
by: He, Xi
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)

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

Computing Approximate Pareto Frontiers for Submodular Utility and Cost Tradeoffs
by: Vombatkere, Karan, et al.
Published: (2026)

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

Approximation Algorithms for Optimal Hopsets
by: Dinitz, Michael, et al.
Published: (2025)

Stability in Graphs with Matroid Constraints
by: Fomin, Fedor V., et al.
Published: (2024)

Approximate Realizations for Outerplanaric Degree Sequences
by: Bar-Noy, Amotz, et al.
Published: (2024)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

An Approximate Generalization of the Okamura-Seymour Theorem
by: Kumar, Nikhil
Published: (2022)

On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2023)

A Constant-Factor Approximation for Directed Latency
by: Blauth, Jannis, et al.
Published: (2025)

On the Structural Parameterizations of 2-Club with Triangle Constraints
by: Jacob, Ashwin, et al.
Published: (2025)

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

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Approximation algorithms for non-sequential star packing problems
by: Hu, Mengyuan, et al.
Published: (2024)