Cover Image

Approximating Submodular Matroid-Constrained Partitioning

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bérczi, Kristóf, Chandrasekaran, Karthekeyan, Király, Tamás, Szabo, Daniel P.
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

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
by: Bérczi, Kristóf, et al.
Published: (2024)

Splitting-off in Hypergraphs
by: Bérczi, Kristóf, et al.
Published: (2023)

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

Rainbow Arborescence Conjecture
by: Bérczi, Kristóf, et al.
Published: (2024)

Approximating maximum-size properly colored forests
by: Bai, Yuhang, et al.
Published: (2024)

Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Inverse matroid optimization under subset constraints
by: Bérczi, Kristóf, et al.
Published: (2025)

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

Multiway Cuts with a Choice of Representatives
by: Bérczi, Kristóf, et al.
Published: (2024)

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

Fault-Tolerant Matroid Bases
by: Bentert, Matthias, et al.
Published: (2025)

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

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

Monotone Submodular Multiway Partition
by: Bi, Richard, et al.
Published: (2024)

A Tale of Santa Claus, Hypergraphs and Matroids
by: Davies, Sami, et al.
Published: (2018)

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

On the Congruency-Constrained Matroid Base
by: Liu, Siyue, et al.
Published: (2023)

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)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)

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)

Holey graphs: very large Betti numbers are testable
by: Szabó, Dániel, et al.
Published: (2024)

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

Cutwidth Bounds via Vertex Partitions
by: Amarilli, Antoine, et al.
Published: (2025)

Edge Clique Partition and Cover Beyond Independence
by: Fomin, Fedor V., et al.
Published: (2025)

Partially Ordered Sets Corresponding to the Partition Problem
by: Kubo, Susumu
Published: (2024)

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

A Uniformly Random Solution to Algorithmic Redistricting
by: Cai, Jin-Yi, et al.
Published: (2024)

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

Hop-Constrained Metric Embeddings and their Applications
by: Filtser, Arnold
Published: (2021)

Fractional Linear Matroid Matching is in quasi-NC
by: Gurjar, Rohit, 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)

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

Matroid Intersection under Minimum Rank Oracle
by: Bárász, Mihály, 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)