A Simple Algorithm for Dynamic Carpooling with Recourse
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913583803138048 |
|---|---|
| author | Efron, Yuval Patel, Shyamal Stein, Cliff |
| author_facet | Efron, Yuval Patel, Shyamal Stein, Cliff |
| contents | We give an algorithm for the fully-dynamic carpooling problem with recourse: Edges arrive and depart online from a graph $G$ with $n$ nodes according to an adaptive adversary. Our goal is to maintain an orientation $H$ of $G$ that keeps the discrepancy, defined as $\max_{v \in V} |\text{deg}_H^+(v) - \text{deg}_H^-(v)|$, small at all times. We present a simple algorithm and analysis for this problem with recourse based on cycles that simplifies and improves on a result of Gupta et al. [SODA '22]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07553 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Simple Algorithm for Dynamic Carpooling with Recourse Efron, Yuval Patel, Shyamal Stein, Cliff Data Structures and Algorithms We give an algorithm for the fully-dynamic carpooling problem with recourse: Edges arrive and depart online from a graph $G$ with $n$ nodes according to an adaptive adversary. Our goal is to maintain an orientation $H$ of $G$ that keeps the discrepancy, defined as $\max_{v \in V} |\text{deg}_H^+(v) - \text{deg}_H^-(v)|$, small at all times. We present a simple algorithm and analysis for this problem with recourse based on cycles that simplifies and improves on a result of Gupta et al. [SODA '22]. |
| title | A Simple Algorithm for Dynamic Carpooling with Recourse |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.07553 |