Cover Image

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Huang, Chien-Chung, Kakimura, Naonori, Kobayashi, Yusuke, Terao, Tatsuya
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Subquadratic Submodular Maximization with a General Matroid Constraint
by: Kobayashi, Yusuke, et al.
Published: (2024)

Faster Approximate Linear Matroid Intersection
by: Terao, Tatsuya
Published: (2026)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
by: Terao, Tatsuya
Published: (2024)

On Approximating the Weighted Region Problem in Square Tessellations
by: Kakimura, Naonori, et al.
Published: (2024)

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
by: Ito, Takehiro, et al.
Published: (2025)

Computing Power Indices in Weighted Majority Games with Formal Power Series
by: Kakimura, Naonori, et al.
Published: (2025)

Reconfiguration of labeled matchings in triangular grid graphs
by: Kakimura, Naonori, et al.
Published: (2024)

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

A Weighted-to-Unweighted Reduction for Matroid Intersection
by: Dudeja, Aditi, et al.
Published: (2026)

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
by: Cervenjak, Philip, et al.
Published: (2026)

Loss Minimization for Electrical Flows over Spanning Trees on Grids
by: Ito, Takehiro, et al.
Published: (2024)

Efficiently Coloring the Intersection of a General Matroid and Partition Matroids
by: Arndt, Stephen, et al.
Published: (2025)

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
by: Kobayashi, Yasuaki, et al.
Published: (2023)

Matroid Intersection under Minimum Rank Oracle
by: Bárász, Mihály, et al.
Published: (2024)

Simultaneous Network Design with Restricted Link Usage
by: Kakimura, Naonori, et al.
Published: (2025)

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
by: Arndt, Stephen, et al.
Published: (2026)

Efficient Matroid Intersection via a Batch-Update Auction Algorithm
by: Blikstad, Joakim, et al.
Published: (2024)

You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
by: Doron-Arad, Ilan, et al.
Published: (2024)

Parameterized Quantum Query Algorithms for Graph Problems
by: Terao, Tatsuya, et al.
Published: (2024)

Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid
by: Diwan, Haya, et al.
Published: (2025)

A PTAS for Weighted Triangle-free 2-Matching
by: Bosch-Calvo, Miguel, et al.
Published: (2026)

Better Approximation for Weighted $k$-Matroid Intersection
by: Singer, Neta, et al.
Published: (2024)

Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
by: Hellerstein, Lisa, et al.
Published: (2026)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
by: Kobayashi, Yusuke, et al.
Published: (2026)

Validating a PTAS for Triangle-Free 2-Matching via a Simple Decomposition Theorem
by: Kobayashi, Yusuke, et al.
Published: (2024)

Structural Parameterizations of $k$-Planarity
by: Gima, Tatsuya, et al.
Published: (2025)

Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion
by: Houari-Durand, Séhane Bel, et al.
Published: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Dynamic Matroids: Base Packing and Covering
by: de Vos, Tijn, et al.
Published: (2025)

Matroid Secretary via Labeling Schemes
by: Bérczi, Kristóf, et al.
Published: (2024)

Sample-Based Matroid Prophet Inequalities
by: Fu, Hu, et al.
Published: (2024)

The $k$-Fold Matroid Secretary Problem
by: Gujjar, Rishi, et al.
Published: (2025)

Forcing a unique minimum spanning tree and a unique shortest path
by: Gima, Tatsuya, et al.
Published: (2025)

Improved Algorithms for Fair Matroid Submodular Maximization
by: Mahabadi, Sepideh, et al.
Published: (2026)

Multiagent Matroid Upgrading: Greedy is Fair and Efficient
by: Ma, Qingwen, et al.
Published: (2026)

On the Parallel Complexity of Finding a Matroid Basis
by: Khanna, Sanjeev, et al.
Published: (2025)

A Refined Kernel for $d$-Hitting Set
by: Liu, Yuxi, et al.
Published: (2025)

The Price of Universal Temporal Reachability
by: Bui-Xuan, Binh-Minh, et al.
Published: (2026)

Improved Online Reachability Preservers
by: Bodwin, Greg, et al.
Published: (2024)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
by: Inamdar, Tanmay, et al.
Published: (2024)