Dynamic Pricing Algorithms for Online Set Cover
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913513505554432 |
|---|---|
| author | Bender, Max Desai, Aum He, Jialin Thompson, Oliver Upreti, Pramithas |
| author_facet | Bender, Max Desai, Aum He, Jialin Thompson, Oliver Upreti, Pramithas |
| contents | We consider dynamic pricing algorithms as applied to the online set cover problem. In the dynamic pricing framework, we assume the standard client server model with the additional constraint that the server can only place prices over the resources they maintain, rather than authoritatively assign them. In response, incoming clients choose the resource which minimizes their disutility when taking into account these additional prices. Our main contributions are the categorization of online algorithms which can be mimicked via dynamic pricing algorithms and the identification of a strongly competitive deterministic algorithm with respect to the frequency parameter of the online set cover input. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15094 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dynamic Pricing Algorithms for Online Set Cover Bender, Max Desai, Aum He, Jialin Thompson, Oliver Upreti, Pramithas Data Structures and Algorithms We consider dynamic pricing algorithms as applied to the online set cover problem. In the dynamic pricing framework, we assume the standard client server model with the additional constraint that the server can only place prices over the resources they maintain, rather than authoritatively assign them. In response, incoming clients choose the resource which minimizes their disutility when taking into account these additional prices. Our main contributions are the categorization of online algorithms which can be mimicked via dynamic pricing algorithms and the identification of a strongly competitive deterministic algorithm with respect to the frequency parameter of the online set cover input. |
| title | Dynamic Pricing Algorithms for Online Set Cover |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.15094 |