Cover Image

An Approximation Algorithm for Monotone Submodular Cost Allocation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Mizutani, Ryuhei
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Problems on Group-labeled Matroid Bases
by: Hörsch, Florian, et al.
Published: (2024)

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

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)

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

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

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

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

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

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

Approximation Algorithms for the $b$-Matching and List-Restricted Variants of MaxQAP
by: Nanta, Jiratchaphat, et al.
Published: (2025)

A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
by: Liang, Wei, et al.
Published: (2024)

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

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

Stable Approximation Algorithms for Dominating Set and Independent Set
by: de Berg, Mark, et al.
Published: (2024)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
by: Bourneuf, Romain, et al.
Published: (2025)

Sandwich Monotonicity and the Recognition of Weighted Graph Classes
by: Beisegel, Jesse, et al.
Published: (2025)

(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)

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

A Constant-Factor Approximation for Directed Latency
by: Blauth, Jannis, 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)

Approximation of Spanning Tree Congestion using Hereditary Bisection
by: Kolman, Petr
Published: (2024)

Approximately covering vertices by order-$5$ or longer paths
by: Gong, Mingyang, et al.
Published: (2024)

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
by: Mömke, Tobias, et al.
Published: (2024)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
by: Swamy, Chaitanya, et al.
Published: (2025)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
by: Disser, Yann, et al.
Published: (2024)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
by: Davies, Sami, et al.
Published: (2023)

Algorithmic Aspects of Temporal Betweenness
by: Buß, Sebastian, et al.
Published: (2020)

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
by: Chakrabarty, Deeparnab, et al.
Published: (2024)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
by: DeHaan, Ian, et al.
Published: (2025)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

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

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

Matching Algorithms in the Sparse Stochastic Block Model
by: Brandenberger, Anna, et al.
Published: (2024)

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

Improved Streaming Algorithm for Fair $k$-Center Clustering
by: Guo, Longkun, et al.
Published: (2025)

Revisiting Tree Isomorphism: An Algorithmic Bric-à-Brac
by: Ingels, Florian
Published: (2023)