Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Proportional Cost Buyback Problem with Weight Bounds
verfasst von : Yasushi Kawase, Xin Han, Kazuhisa Makino
Erschienen in: Combinatorial Optimization and Applications
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
Abstract
In this paper, we study the proportional cost buyback problem. The input is a sequence of elements \(e_1,e_2,\dots ,e_n\), each of which has a weight \(w(e_i)\). We assume that weights have an upper and a lower bound, i.e., \(l\le w(e_i)\le u\) for any \(i\). Given the ith element \(e_i\), we either accept \(e_i\) or reject it with no cost, subject to some constraint on the set of accepted elements. During the iterations, we could cancel some previously accepted elements at a cost that is proportional to the total weight of them. Our goal is to maximize the profit, i.e., the sum of the weights of elements kept until the end minus the total cancellation cost occurred. We consider the matroid and unweighted knapsack constraints. For either case, we construct optimal online algorithms and prove that they are the best possible.