Name
Abstract | ||
|---|---|---|
In the k-search problem, a player is searching for the k highest (respectively, lowest) prices in a sequence, which is revealed to her sequentially. At each quotation, the player
has to decide immediately whether to accept the price or not. Using the competitive ratio as a performance measure, we give optimal deterministic and
randomized algorithms for both the maximization and minimization problems, and discover that the problems behave substantially
different in the worst-case. As an application of our results, we use these algorithms to price “lookback options”, a particular
class of financial derivatives. We derive bounds for the price of these securities under a no-arbitrage assumption, and compare
this to classical option pricing. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00453-008-9217-8 | Algorithmica - Special Issue: European Symposium on Algorithms 2007, Guest Editors: Larse Arge and Emo Welzl |
Keywords | Field | DocType |
particular class,k-search problem,lookback option,competitive ratio,minimization problem,performance measure,classical option pricing,Optimal Algorithms,financial derivative,optimal deterministic,no-arbitrage assumption,Option Pricing | Online algorithm,Approximation algorithm,Mathematical economics,Mathematical optimization,Reservation price,Search algorithm,Valuation of options,Computer science,Algorithm,Combinatorial optimization,Maximization,Competitive analysis | Journal |
Volume | Issue | ISSN |
55 | 2 | 0178-4617 |
Citations | PageRank | References |
25 | 1.46 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julian Lorenz | 1 | 27 | 2.77 |
| Konstantinos Panagiotou | 2 | 290 | 27.80 |
| Angelika Steger | 3 | 995 | 111.50 |