Imagen de Portada

Beating Competitive Ratio 4 for Graphic Matroid Secretary

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Banihashem, Kiarash, Hajiaghayi, MohammadTaghi, Kowalski, Dariusz R., Krysta, Piotr, Mittal, Danny, Olkowski, Jan
Formato:	Preprint
Publicado:	2025
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

Optimal Algorithms for Free Order Multiple-Choice Secretary
por: Hajiaghayi, Mohammad Taghi, et al.
Publicado: (2022)

Dynamic Metric Embedding into $\ell_p$ Space
por: Banihashem, Kiarash, et al.
Publicado: (2024)

Matroid Algorithms Under Size-Sensitive Independence Oracles
por: Banihashem, Kiarash, et al.
Publicado: (2026)

Online Sampling and Decision Making with Low Entropy
por: Hajiaghayi, Mohammad Taghi, et al.
Publicado: (2021)

A Dynamic Algorithm for Weighted Submodular Cover Problem
por: Banihashem, Kiarash, et al.
Publicado: (2024)

Bandit Social Learning: Exploration under Myopic Behavior
por: Banihashem, Kiarash, et al.
Publicado: (2023)

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
por: Banihashem, Kiarash, et al.
Publicado: (2025)

Replicable Composition
por: Banihashem, Kiarash, et al.
Publicado: (2026)

Pandora with Inaccurate Priors
por: Banihashem, Kiarash, et al.
Publicado: (2025)

Active Learning for Decision Trees with Provable Guarantees
por: Moakhar, Arshia Soltani, et al.
Publicado: (2026)

Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed?
por: Hajiaghayi, Mohammad T., et al.
Publicado: (2024)

Adversarially Robust Approximate Furthest Neighbor
por: Banihashem, Kiarash, et al.
Publicado: (2026)

Bi-Criteria Metric Distortion
por: Banihashem, Kiarash, et al.
Publicado: (2024)

2-Approximation for Prize-Collecting Steiner Forest
por: Ahmadi, Ali, et al.
Publicado: (2023)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
por: Ahmadi, Ali, et al.
Publicado: (2025)

Prize-Collecting Forest with Submodular Penalties: Improved Approximation
por: Ahmadi, Ali, et al.
Publicado: (2025)

Prize-Collecting Steiner Tree: A 1.79 Approximation
por: Ahmadi, Ali, et al.
Publicado: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
por: Das, Debarati, et al.
Publicado: (2025)

Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
por: Kowalski, Dariusz R., et al.
Publicado: (2025)

Replication-proof Bandit Mechanism Design with Bayesian Agents
por: Shin, Suho, et al.
Publicado: (2023)

Optimal Contest Beyond Convexity
por: Golrezaei, Negin, et al.
Publicado: (2026)

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

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

Fairness and Efficiency in Online Class Matching
por: Hajiaghayi, MohammadTaghi, et al.
Publicado: (2024)

Delegation with Costly Inspection
por: Hajiaghayi, Mohammad T., et al.
Publicado: (2025)

The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends
por: Blank, Lotte, et al.
Publicado: (2025)

Additively Competitive Secretaries
por: Mahdian, Mohammad, et al.
Publicado: (2026)

Towards Efficient Data Structures for Approximate Search with Range Queries
por: Kian, Ladan, et al.
Publicado: (2026)

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

Laminar Matroid Secretary: Greedy Strikes Back
por: Huang, Zhiyi, et al.
Publicado: (2023)

Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications
por: De Marco, Gianluca, et al.
Publicado: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
por: Khanna, Sanjeev, et al.
Publicado: (2025)

Optimal $k$-Secretary with Logarithmic Memory
por: Qiao, Mingda, et al.
Publicado: (2025)

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

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

A Tight Competitive Ratio for Online Submodular Welfare Maximization
por: Ganz, Amit, et al.
Publicado: (2023)

Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources
por: Goyal, Vineet, et al.
Publicado: (2020)

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
por: Ma, Will, et al.
Publicado: (2019)

Fair Secretaries with Unfair Predictions
por: Balkanski, Eric, et al.
Publicado: (2024)

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