Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Competitive Analysis of Bi-directional Non-preemptive Conversion
Speaker:Günter Schmidt
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 23 November 2017
Duration:30 Minutes
Building:E1 4

In an online conversion problem a player is converting one asset into another, e.g. dollars to yen, based on a finite sequence of unknown future conversion rates. When a new rate is announced the player must decide how many dollars(yen) to convert to yen (dollars) according to this rate. Conversion is over when the last rate has appeared. The objective is to maximize terminal wealth after conversion.

In uni-directional conversion dollars are converted to yen and in bi-directional conversion not only dollars to yen but also yen to dollars may be converted. If all current wealth has to be converted at one rate we call the problem non-preemptive; if parts of the current wealth can be converted at one rate we call it preemptive. We assume that lower and upper bounds on conversion rates are given.

Uni-directional preemptive and non-preemptive and bi-directional preemptive conversion is investigated in El Yaniv et al. (Proceeding 33rd annual symposium on Foundations of Computer Science, pp 327–333, 1992, Algorithmica 30:101–139, 2001). Their results for bi-directional preemptive conversion are improved by Dannoura and Sakurai (Inf Process Lett 66:27–33, 1998). The suggested improvement is conjectured not to be optimal for bi-directional preemptive conversion. There are no results for optimal bi-directional non-preemptive conversion.

We investigate the problem of bi-directional non-preemptive online conversion. We present lower bounds, upper bounds and an optimal algorithm to solve the problem. Moreover, we prove that the algorithm of Dannoura and Sakurai 1998 is not optimal for bi-directional preemptive conversion.

Name(s):Yun Kuen Cheung
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Yun Kuen Cheung, 10/22/2017 02:07 PM
Last modified:
Uwe Brahm/MPII/DE, 11/23/2017 07:01 AM
  • Yun Kuen Cheung, 10/22/2017 02:09 PM
  • Yun Kuen Cheung, 10/22/2017 02:07 PM -- Created document.