Buchumschlag

Matroid Secretary via Labeling Schemes

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bérczi, Kristóf, Livanos, Vasilis, Soto, José, Verdugo, Victor
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Free-order secretary for two-sided independence systems
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

Approximating Submodular Matroid-Constrained Partitioning
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

The $k$-Fold Matroid Secretary Problem
von: Gujjar, Rishi, et al.
Veröffentlicht: (2025)

Matroid Intersection under Minimum Rank Oracle
von: Bárász, Mihály, et al.
Veröffentlicht: (2024)

Minimization I.I.D. Prophet Inequality via Extreme Value Theory: A Unified Approach
von: Livanos, Vasilis, et al.
Veröffentlicht: (2024)

Beating Competitive Ratio 4 for Graphic Matroid Secretary
von: Banihashem, Kiarash, et al.
Veröffentlicht: (2025)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
von: Bai, Yuhang, et al.
Veröffentlicht: (2026)

Approximating maximum properly colored forests via degree bounded independent sets
von: Bai, Yuhang, et al.
Veröffentlicht: (2025)

Inverse matroid optimization under subset constraints
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

Multiway Cuts with a Choice of Representatives
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Laminar Matroid Secretary: Greedy Strikes Back
von: Huang, Zhiyi, et al.
Veröffentlicht: (2023)

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

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Splitting-off in Hypergraphs
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2023)

Finding Spanning Trees with Perfect Matchings
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Improved Mechanisms and Prophet Inequalities for Graphical Dependencies
von: Livanos, Vasilis, et al.
Veröffentlicht: (2024)

Optimal $k$-Secretary with Logarithmic Memory
von: Qiao, Mingda, et al.
Veröffentlicht: (2025)

Approximating maximum-size properly colored forests
von: Bai, Yuhang, et al.
Veröffentlicht: (2024)

Rainbow Arborescence Conjecture
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Prophet Upper Bounds for Online Matching and Auctions
von: Soto, José, et al.
Veröffentlicht: (2024)

Efficiently Coloring the Intersection of a General Matroid and Partition Matroids
von: Arndt, Stephen, et al.
Veröffentlicht: (2025)

Optimal Algorithms for Free Order Multiple-Choice Secretary
von: Hajiaghayi, Mohammad Taghi, et al.
Veröffentlicht: (2022)

Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
von: Hellerstein, Lisa, et al.
Veröffentlicht: (2026)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
von: Long, Yaowei, et al.
Veröffentlicht: (2024)

Efficient Matroid Intersection via a Batch-Update Auction Algorithm
von: Blikstad, Joakim, et al.
Veröffentlicht: (2024)

New Oracles and Labeling Schemes for Vertex Cut Queries
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

Fair Secretaries with Unfair Predictions
von: Balkanski, Eric, et al.
Veröffentlicht: (2024)

Sample-Based Matroid Prophet Inequalities
von: Fu, Hu, et al.
Veröffentlicht: (2024)

Dynamic Matroids: Base Packing and Covering
von: de Vos, Tijn, et al.
Veröffentlicht: (2025)

Faster Approximate Linear Matroid Intersection
von: Terao, Tatsuya
Veröffentlicht: (2026)

On the Parallel Complexity of Finding a Matroid Basis
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Improved Algorithms for Fair Matroid Submodular Maximization
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2026)

A Weighted-to-Unweighted Reduction for Matroid Intersection
von: Dudeja, Aditi, et al.
Veröffentlicht: (2026)

Multiagent Matroid Upgrading: Greedy is Fair and Efficient
von: Ma, Qingwen, et al.
Veröffentlicht: (2026)

Subquadratic Submodular Maximization with a General Matroid Constraint
von: Kobayashi, Yusuke, et al.
Veröffentlicht: (2024)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
von: Inamdar, Tanmay, et al.
Veröffentlicht: (2024)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
von: Eisenbrand, Friedrich, et al.
Veröffentlicht: (2024)

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection
von: Huang, Chien-Chung, et al.
Veröffentlicht: (2026)

Matroid-Based TSP Rounding for Half-Integral Solutions
von: Gupta, Anupam, et al.
Veröffentlicht: (2021)

Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting
von: Ganczorz, Adam, et al.
Veröffentlicht: (2025)