Imagen de Portada

Lower Bounds for Matroid Optimization Problems with a Linear Constraint

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Doron-Arad, Ilan, Kulik, Ariel, Shachnai, Hadas
Formato:	Preprint
Publicado:	2023
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
por: Doron-Arad, Ilan, et al.
Publicado: (2023)

Fine Grained Lower Bounds for Multidimensional Knapsack
por: Doron-Arad, Ilan, et al.
Publicado: (2024)

Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
por: Kulik, Ariel, et al.
Publicado: (2019)

Unsplittable Flow on a Short Path
por: Doron-Arad, Ilan, et al.
Publicado: (2024)

Approximations and Hardness of Packing Partially Ordered Items
por: Doron-Arad, Ilan, et al.
Publicado: (2024)

An Algorithm-to-Contract Framework without Demand Queries
por: Doron-Arad, Ilan, et al.
Publicado: (2025)

Non-Linear Paging
por: Doron-Arad, Ilan, et al.
Publicado: (2024)

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
por: Esmer, Barış Can, et al.
Publicado: (2024)

Faster Approximate Linear Matroid Intersection
por: Terao, Tatsuya
Publicado: (2026)

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

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

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

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
por: Manea, Florin, et al.
Publicado: (2024)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
por: Eisenbrand, Friedrich, et al.
Publicado: (2024)

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

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

A Poisson Process for Submodular Maximization
por: Rozenman, Amit Ganz, et al.
Publicado: (2026)

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

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

Linear Space Streaming Lower Bounds for Approximating CSPs
por: Chou, Chi-Ning, et al.
Publicado: (2021)

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

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

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
por: Yoshida, Yuichi
Publicado: (2026)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
por: Boneh, Itai, et al.
Publicado: (2025)

New Algorithms and Lower Bounds for Streaming Tournaments
por: Ghosh, Prantar, et al.
Publicado: (2024)

Lower Bounds on $0$-Extension with Steiner Nodes
por: Chen, Yu, et al.
Publicado: (2024)

Double Exponential Lower Bound for Telephone Broadcast
por: Tale, Prafullkumar
Publicado: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
por: Chen, Yu, et al.
Publicado: (2026)

Dynamic PageRank: Algorithms and Lower Bounds
por: Jayaram, Rajesh, et al.
Publicado: (2024)

Lower Bounds for Linear Operators
por: Ko, Young Kun
Publicado: (2025)

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

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

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

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

Improved Lower Bounds for Privacy under Continual Release
por: Aryanfard, Bardiya, et al.
Publicado: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
por: Fleming, Noah, et al.
Publicado: (2026)

Lower Bounds for Non-adaptive Local Computation Algorithms
por: Azarmehr, Amir, et al.
Publicado: (2025)

A Lower Bound for Light Spanners in General Graphs
por: Bodwin, Greg, et al.
Publicado: (2024)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
por: Huiberts, Sophie, et al.
Publicado: (2022)