Queueing Colloquium at CWI

 

Date: Friday, April 19, 2013

Location: CWI, L016 (ground floor)

Address: Science Park 123, Amsterdam

 

The program is as follows:

 

11.00 - 11.45 Arnoud den Boer (Eindhoven University of Technology and University of Amsterdam)

Online learning in dynamic pricing

 

11.45 - 12.30 Nelly Litvak (University of Twente)

Uncovering the network structure in Big Data

 

12.30 - 13.45 Lunch

 

13.45 - 14.30 Josh Reed (Stern School of Business - New York University)

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 (Eindhoven University of Technology)

Lingering issues in distributed scheduling

 

16.15 – 17.00 Daan Crommelin (CWI)

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

 

http://www.cwi.nl/~bertz

http://www.cwi.nl/~sindo

 

 

Public transportation:

Train station: Amsterdam Science Park - 3 minute walk from CWI.

 

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 (Eindhoven University of Technology and University of Amsterdam)

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 (University of Twente)

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 (Stern School of Business - New York University)

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 (Eindhoven University of Technology)

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 (CWI)

Stochastic methods in atmosphere-ocean science

 

TBA