ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    ISSN: 1432-5217
    Keywords: Key words: Conservation laws ; Gittins index ; LP relaxation ; multi-armed bandit ; performance space ; undiscounted tax problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract. A radically new approach to indexable systems pioneered by Bertsimas and Niño-Mora is utilised to provide novel analyses of classes of complex multi-armed bandits in which the individual bandits have their own decision structure. A new index result for an undiscounted model is established. Parallel server versions of the models are studied via (the dual of) an LP relaxation. This analysis yields a natural heuristic policy which is evaluated numerically.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Computing 56 (1996), S. 95-104 
    ISSN: 1436-5057
    Keywords: 68M20 ; Probabilistic algorithm ; online scheduling ; interval ; busy time
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Wir betrachten das Problem der Zuteilung von Aufgaben bestimmter Rechenzeit auf einem Rechner, um so seine Auslastung zu maximieren. Die Aufgabe besteht darin, einen probabilistischen Online-Algorithmus mit vernünftigem worst-case Performance-Verhältnis zu finden. Wir geben die Antwort auf ein offenes Problem von Lipton und Tompkins, das das bestmögliche Verhältnis betrifft. Weiter verallgemeinern wir ihre Ergebnisse auf einm-Maschinen-Analogon. Schließlich wird eine Variante des Problems analysiert, in dem der Rechner mit einem Zwischenspeicher für einen Job versehen ist.
    Notes: Abstract We consider the problem of scheduling tasks requiring certain processing times on one machine so that the busy time of the machine is maximized. The problem is to find a probabilistic online algorithm with reasonable worst case performance ratio. We answer an open problem of Lipton and Tompkins concerning the best possible ratio that can be achieved. Furthermore, we extend their results to anm-machine analogue. Finally, a variant of the problem is analyzed, in which the machine is provided with a buffer to store one job.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 3
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract When controlled stochastic systems have performances which satisfy generalisedconservation laws (GCL), an objective which is linear in the performance is optimised by aGittins index policy. We develop measures of the extent to which a system fails to satisfyGCL and derive suboptimality bounds for suitable index policies in terms of such measures.These bounds are used, inter alia, to explore the robustness in performance of cm‐typerules for a multiclass G/G/1 queueing system to departures from an assumption of exponentialservice times. We also study Gittins index policies for parallel processor versions of theclassical undiscounted and discounted multi‐armed bandit problems. In the undiscountedcase, the cost of an index policy comes within a constant of the optimal cost ‐ thisconstant being independent of the number of projects submitted for scheduling. In thediscounted case, under fairly mild conditions, Gittins index policies come within an O(1) quantity ofoptimality and are hence average reward optimal when the discount rate is small enough.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...