Tree Bounds for Sums of Bernoulli Random Variables: A Linear Optimization Approach

We study the problem of computing the tightest upper and lower bounds on the probability that the sum of n dependent Bernoulli random variables exceeds an integer k. Under knowledge of all pairs of bivariate distributions denoted by a complete graph, the bounds are NP-hard to compute. When the bivariate distributions are specified on a … Read more

Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results

As a consequence of the liberalisation of the European gas market in the last decades, gas trading and transport have been decoupled. At the core of this decoupling are so-called bookings and nominations. Bookings are special capacity right contracts that guarantee that a specified amount of gas can be supplied or withdrawn at certain entry … Read more

Location Routing Problems on Simple Graphs

This paper addresses combined location/routing problems defined on trees. Several problems are studied, which consider service demand both at the vertices and the edges of the input tree. Greedy type optimal heuristics are presented for the cases when all vertices have to be visited and facilities have no set-up costs. Facilities set-up costs can also … Read more

Speeding up dynamic shortest path algorithms

Dynamic shortest path algorithms update the shortest paths to take into account a change in an edge weight. This paper describes a new technique that allows the reduction of heap sizes used by several dynamic shortest path algorithms. For unit weight change, the updates can be done without heaps. These reductions almost always reduce the … Read more