Copertina

The Power of Greedy for Online Minimum Cost Matching on the Line

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Balkanski, Eric, Faenza, Yuri, Perivier, Noemie
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Energy-Efficient Scheduling with Predictions
di: Balkanski, Eric, et al.
Pubblicazione: (2024)

Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line
di: Kuo, Tung-Wei
Pubblicazione: (2024)

MNL-Bandit with Knapsacks: a near-optimal algorithm
di: Aznag, Abdellah, et al.
Pubblicazione: (2021)

Learning-Augmented Dynamic Submodular Maximization
di: Agarwal, Arpit, et al.
Pubblicazione: (2023)

Greedy Dynamic Matching
di: Arnosti, Nick, et al.
Pubblicazione: (2025)

Expected Cost of Greedy Online Facility Assignment on Regular Polygons (v3)
di: Riad, Md. Rawha Siddiqi, et al.
Pubblicazione: (2025)

On the Advice Complexity of Online Matching on the Line
di: Csaba, Béla, et al.
Pubblicazione: (2024)

Fair Secretaries with Unfair Predictions
di: Balkanski, Eric, et al.
Pubblicazione: (2024)

Online Matching with Delays and Size-based Costs
di: Kawase, Yasushi, et al.
Pubblicazione: (2024)

Learning Low Degree Hypergraphs
di: Balkanski, Eric, et al.
Pubblicazione: (2022)

Potential-Based Greedy Matching for Dynamic Delivery Pooling
di: Ma, Hongyao, et al.
Pubblicazione: (2025)

Submodular Maximization in Exactly $n$ Queries
di: Balkanski, Eric, et al.
Pubblicazione: (2024)

A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
di: Derakhshan, Mahsa, et al.
Pubblicazione: (2026)

Learning Minimum Linear Arrangement of Cliques and Lines
di: Dallot, Julien, et al.
Pubblicazione: (2024)

Minimum-Peak-Cost Flows Over Time
di: Anapolska, Mariia, et al.
Pubblicazione: (2025)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
di: Jiang, Tianle, et al.
Pubblicazione: (2024)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
di: Bhore, Sujoy, et al.
Pubblicazione: (2023)

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
di: Arkhipov, Pavel, et al.
Pubblicazione: (2026)

New Greedy Spanners and Applications
di: Popova, Elizaveta, et al.
Pubblicazione: (2026)

The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner
di: Chen, Yeyuan
Pubblicazione: (2024)

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
di: Davies-Peck, Peter
Pubblicazione: (2026)

Greedy BST on Permutation Initial Tree
di: Pareek, Akash
Pubblicazione: (2024)

From Dynamic Programs to Greedy Algorithms
di: van Melkebeek, Dieter
Pubblicazione: (2025)

Online Matching: A Brief Survey
di: Huang, Zhiyi, et al.
Pubblicazione: (2024)

Online Matching in Geometric Random Graphs
di: Sentenac, Flore, et al.
Pubblicazione: (2023)

Online Drone Coverage of Targets on a Line
di: Dobrev, Stefan, et al.
Pubblicazione: (2026)

Online General Knapsack with Reservation Costs
di: Burjons, Elisabet, et al.
Pubblicazione: (2025)

Minimum Cost Adaptive Submodular Cover
di: Al-Thani, Hessa, et al.
Pubblicazione: (2022)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
di: Brand, Jan van den, et al.
Pubblicazione: (2025)

Engineering Algorithms for Dynamic Greedy Set Cover
di: Uzrad, Amitai
Pubblicazione: (2026)

Greedy Completion for Weighted $(α,β)$-Spanners
di: Tzalik, Elad
Pubblicazione: (2026)

An Improved Greedy Approximation for (Metric) $k$-Means
di: Charikar, Moses, et al.
Pubblicazione: (2026)

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

Almost Tight Bounds for Online Hypergraph Matching
di: Tröbst, Thorben, et al.
Pubblicazione: (2024)

Online Metric Matching: Beyond the Worst Case
di: Yang, Mingwei, et al.
Pubblicazione: (2024)

A Lossless Deamortization for Dynamic Greedy Set Cover
di: Solomon, Shay, et al.
Pubblicazione: (2024)

A Threshold Greedy Algorithm for Noisy Submodular Maximization
di: Chen, Wenjing, et al.
Pubblicazione: (2023)

Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching
di: Ma, Will
Pubblicazione: (2024)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
di: Joseph, et al.
Pubblicazione: (2023)

Simple Construction of Greedy Trees and Greedy Permutations
di: Chubet, Oliver, et al.
Pubblicazione: (2024)