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 SimulationsCaner 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

graph K

graph K

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

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.

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

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.