abstracts2005

Asymptotic optimality of a time-dependent controlled queue

Milica Cudina

We consider a control problem involving a time-dependent queue on a
finite time horizon. The performance measure penalizes for the work lost due to the fact that
the buffer at the service station is finite. The constraints are given in terms of
total available service. Using strong approximations, a class of asymptotically optimal
disciplines is determined. The analysis is conducted both in the fluid as well as in the second
order (``diffusion") regime. The latter requires an appropriate extension of the usual notion of
asymptotic optimality for time-homogenous systems in heavy traffic to the time-inhomogenous context.
Finally, we identify controls that are asymptotically optimal for the sequence of prelimit systems
in the uniform acceleration regime.

A Multiscale Approach to Control Variates for Monte Carlo Simulation

Adam Speight

Variance reduction techniques are often used to improve
the performance of the crude Monte Carlo integration method.
This talk presents a method to extend the applicability of a prominent
variance reduction technique known as control variates. This new method
is shown to affect substantial variance reduction when a control variate
is available that is both highly correlated with the quantity of
interest and relatively cheap to simulate. To illustrate the method, we
price Asian options in the Black-Scholes framework and European options
in Heston's model of stochastic volatility. In both cases, variance is
reduced by a factor of about four compared to the crude Monte Carlo
estimate.

***********************************************************************

Understanding Living Systems through Mathematics and Computer Simulations

Caner Kazanci

Recent advances in data acquisition techniques have resulted in vast
amounts of quantitative information on living systems. Mathematical
tools are needed to interpret these massive data into useful knowledge
for designing new therapies and drugs. In this talk I will discuss some
challenges in biology and their translation into mathematical problems.
Some of these problems do not have analytical solutions and require
numerical methods and computer simulations. The complexity of even the
simplest examples of biological systems (such as bacteria) require the
use of features from various fields in mathematics such as ordinary,
partial,
and stochastic differential equations; dynamical systems; numerical
analysis and graph theory.

I will focus on questions regarding the complexity of living cells, which
we model as large-scale biochemical reaction systems. We use this model
to investigate the statistical properties of living systems, such as the
abundance of the molecules in the system at steady state. Surprisingly,
we find that this distribution is insensitive to initial conditions,
reaction constants and network connectivity. Many of our findings match
with experimental results on organisms from E.Coli to human.

***********************************************************************

Hamilton cycles in random lifts of complete graphs

Kelley Burgin

An n-lift of a graph K, is a graph with vertex set V(K)x[n] and for each edge (i,j) in E(K)
there is a perfect matching between {i}x[n] and {j}x[n]. If these matchings are chosen
independently and uniformly at random then we say that we have a random n-lift. We
show that there are constants h₁,h₂ such that if h>h₁ then a random n-lift of the complete
graph K_his hamiltonian whp and if h>h₂ then a random n-lift of the complete bipartite
graph K_h,h is hamiltonian whp.

***********************************************************************

Random 2-SAT Does not depend on a giant

David Kravitz

Here we introduce a new model for random $2-SAT$. It is
well-known that on the standard model there is a sharp phase
transition, the probability of satisfiability quickly drops as the
number of clauses exceeds the number of variables. The location of
this phase transition suggests that there is a direct connection
between the appearance of a giant in the corresponding $2n$-vertex
graph and satisfiability. Here we show that the giant has nothing
to do with satisfiability, and in fact the expected degree of a
randomly chosen vertex is the important thing.

***********************************************************************

The Maximal Independence Set Problem: Copositive Programming

Juan Vera

The maximum independence set problem is a central problem in
combinatorial optimization, and has been the subject of extensive study. In addition to being
a classical NP-hard problem, the maximum independence set is among the provably hardest
combinatorial problems to approximate.

De Klerk and Pasechnik proposed two alternative approximation schemes to the problem. Their
approach is based on a characterization of the independence number via copositive programming,
combined with a successive approximation procedure for the copositive cone inspired by the work
of Parrilo. We refine the results of De Klerk and Pasechnik concerning the approximations to the i
ndependence number. In this talk I will introduce copositive programming, and explain our results.
The talk will be at the introductory level.

***********************************************************************

Stephen J. D'Silva

We study convex risk measures which are both time consistent and
currency invariant in a discrete time, finite horizon framework.
We define currency invariance for monetary and non-monetary convex
risk measures. We show that only trivial monetary convex risk
measures satisfy both time consistency and currency invariance for
all positive bounded currency exchange rate processes. We propose
a class of non-monetary convex risk measures. We weaken the
definition of time consistency, as defined in Artzner et al.
(2003), to hold only for discrete dates and call this weak time
consistency. We develop a representation for weakly time
consistent non-monetary convex risk measures. We show that all
non-monetary time consistent coherent risk measures are currency
invariant.

***********************************************************************

Konstantin Andreev

Simultaneous Source Location

Abstract: In this talk we consider the problem of Simultaneous Source
Location -- selecting locations for sources in a
capacitated graph such that a given set of demands can be satisfied. We
give an exact algorithm for trees and show how this can be combined with a
result of H. Raecke to give an approximation algorithm that exceeds edge
capacities by at most O(log^2 n log log n), where n is the number of nodes.
We will describe the notion of graph treewidth and show that on graphs of
bounded treewidth the problem is still NP-Hard. We will give a
PTAS with at most O(1+epsilon) violation of the capacities, or a
(k+1)-approximation with exact capacities, where k is the treewidth and
epsilon can be made arbitrarily small.