Queueing Colloquium at CWI
Date:
Friday, April 19, 2013
Location:
CWI, L016 (ground floor)
Address:
The
program is as follows:
11.00 - 11.45 Arnoud den Boer (
Online
learning in dynamic pricing
11.45
- 12.30 Nelly Litvak (
Uncovering
the network structure in Big Data
12.30
- 13.45 Lunch
13.45
- 14.30 Josh Reed (
High
frequency asymptotics for the limit order book
14.30
– 15.15 Neil Walton (University of Amsterdam)
Stability
of MaxWeight-(α,g)
15.15 – 15.30 Coffee
break
15.30
- 16.15 Florian Simatos (
Lingering
issues in distributed scheduling
16.15 – 17.00 Daan Crommelin (
Stochastic
methods in atmosphere-ocean science
17.00
Reception
For
further information, do not hesitate to contact us.
Bert
Zwart and Sindo Núñez
Queija
Public
transportation:
Train station:
Lines 40 and 240 offer a convenient bus
service to CWI, from Amstel (both lines) and Muiderpoort
(only line 40) stations.
From Amstel station, the buses leave from the
upper side of the station. From Muiderpoort station
the buses leave from
Insulindelaan. In both cases the ride takes approximately 5 minutes. The bus stops in
front of CWI (Science Park 123).
Abstracts
Arnoud den Boer (
Online
learning in dynamic pricing
We consider online learning in dynamic
pricing problems where the price-demand relation is unknown and can be learned
from accumulating sales data. In these
problems the classical trade-off between exploration and exploitation plays a
central role: typically, a certain amount of price experimentation (deviating
from the perceived optimal price) is necessary to obtain optimal performance.
We show in a multiple-product infinite-inventory setting what is the optimal
amount of exploration, and show that this leads to a cost-for-learning that
grows as the square-root of the length of the selling horizon. We also consider
a single-product finite-inventory setting, relevant to e.g. pricing of airline
tickets. We show that in this setting no price experimentation is necessary,
and that the cost-for-learning of a simple myopic pricing policy grows only
logarithmically in the length of the selling horizon. We discuss the
differences between these two models that cause this qualitatively different behavior of the cost-for-learning.
Nelly
Litvak (
Uncovering
the network structure in Big Data
I will discuss two problems in the analysis
of large complex networks such as world wide web and on-line social networks.
1. The first problem is in quickly finding top k lists of nodes with the largest
degrees in large complex networks when the structure of the network in unknown,
for example, as in Twitter network. If the adjacency list of the network is
known (not often the case in complex networks), a deterministic algorithm to
find a node with the largest degree requires an average complexity of O(n),
where n is the number of nodes in the network. Even this modest complexity can
be very high for large complex networks. We propose to use the random walk
based method that enables computational savings of orders of magnitude, and
derive stopping criteria.
2. The second problem is in measuring
dependencies between degrees of neighbouring nodes. One of the problems with
the commonly used assortativity coefficient is that
{in disassortative networks its magnitude decreases
with the network size. This makes it impossible to compare mixing patterns, for
example, in two web crawls of different size.
We show the assortativity coefficient is
non-negative in the large graph limit when the degree distribution has an
infinite third moment. Then we consider the alternative degree-degree
dependency measure, based on the Spearman's rho, and prove that it converges to
an appropriate limit under very general conditions. We verify that these
conditions hold in common network models, such as configuration model and
Preferential Attachment model. We conclude that rank correlations provide a
suitable and informative method for uncovering network mixing patterns.
This is a joint work with Konstantin Avrachenkov, Marina Sokol and Remco van der Hofstad
Josh
Reed (
High
frequency asymptotics for the limit order book
We study the one-sided limit order book for sell (or buy) orders
and model it as a measure-valued process. Limit orders arrive to the book
according to a Poisson process and are placed on the book according to a
distribution which varies depending on the current best price. Market orders to
buy (or sell) periodically arrive to the book according to a second,
independent Poisson process and remove from the book the order corresponding to
the current best price. We consider the above described order book in a high
frequency regime in which the rate of incoming limit and market orders is large
and traders place their limit sell orders close to the current best price. Our
first set of results provide weak limits for the price process and the properly
scaled measure-valued order book process in the high frequency regime. In
particular, we characterize the limiting measure-valued order book process as
the solution to a measure-valued stochastic differential equation. We then
provide an analysis of both the transient and long-run behavior of the limiting
order book process. This is joint work with Peter Lakner
and Sasha Stoikov.
Neil
Walton (University of Amsterdam)
Stability
of MaxWeight-(α,g)
We consider a single-hop switched queueing network. Amongst a plethora of applications, these
networks have been used to model wireless networks and input queued switches.
The MaxWeight scheduling policies have proved
popular, chiefly, because they are throughput optimal and do not require
explicit estimation of arrival rates.
In this article, we prove the same
throughput optimality property for a generalization of the MaxWeight
policy called the MaxWeight-({\alpha},g) policy.
These throughput optimal, myopic scheduling policies allow for scheduling
choices similar to those found in bandwidth sharing networks -- a further well
studied model of Internet congestion.
Florian
Simatos (
Lingering
issues in distributed scheduling
Recent advances have resulted in
queue-based algorithms for medium access control which operate in a distributed
fashion, and yet achieve the optimal throughput performance of centralized
scheduling algorithms. However, fundamental performance bounds reveal that the "cautious"
activation rules involved in establishing throughput optimality tend to produce
extremely large delays, typically growing exponentially in 1/(1-r), with r the
load of the system, in contrast to the usual linear growth.
Motivated by that issue, I will discuss in
this talk the extent to which more "aggressive" schemes can improve
the delay performance. In the simplest possible scenario, I will show how
aggressive activation rules induce a lingering effect, where individual nodes
retain possession of a shared resource for excessive lengths of time even while
a majority of other nodes idle. Using central limit theorem type arguments, it
can be proved that the idleness induced by the lingering effect may cause the
delays to grow with 1/(1-r) at a quadratic rate.
Daan Crommelin (
Stochastic
methods in atmosphere-ocean science
TBA