2013 | OriginalPaper | Buchkapitel
Together or Separate? Algorithmic Aggregation Problems
verfasst von : Marek Chrobak
Erschienen in: Fundamentals of Computation Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Aggregation problems arise when an expensive resource is shared by multiple agents. Shared access to this resource may result in agents incurring additional expenses, for example due to excessive wait time. This leads to a tradeoff between the frequency of access to the shared resource and the overhead costs for individual agents. Some participants of FCT may face this dilemma when heading to the airport after the conference. Sharing a cab saves overall cost, but it may create some inconvenience, or even additional expenses, if it results in an early or late arrival at the airport.
Aggregation problems of this nature are ubiquitous. For example, in the
TCP Acknowledgment Problem
in networks, control acknowledgement packets can be aggregated and transmitted together. This reduces network traffic, but it can also result in undesirable delays and complicate congestion control. In the
Joint Replenishment Problem
, extensively studied in the operations research area, retailers place orders for a commodity at the supplier. To satisfy these orders, the supplier sends shipments of the commodity to a shared warehouse, which then redistributes them to the suppliers. The objective is to minimize the total shipment cost and the retailers’ cost of waiting for their shipments.
This talk will survey the existing work on efficient algorithms for such aggregation problems, attempting to provide a unified perspective and emphasizing connections between different variants. We will discuss both offline and online algorithms, focussing mostly on recent results on approximation algorithms for these problems and on the remaining open problems.