Semidefinite approximations for bicliques and biindependent pairs

\(\) We investigate some graph parameters asking to maximize the size of biindependent pairs (A,B) in a bipartite graph G = (V1 \cup V2;E), where A\subseteq V1, B \subseteq V2 and A \cup B is independent. These parameters also allow to study bicliques in general graphs (via bipartite double graphs). When the size is the … Read more

Dynamic Node Packing

We propose a dynamic version of the classical node packing problem, also called the stable set or independent set problem. The problem is defined by a node set, a node weight vector, and an edge probability vector. For every pair of nodes, an edge is present or not according to an independent Bernoulli random variable … Read more

On an open question about the complexity of a dynamic spectrum management problem

In this paper we discuss the complexity of a dynamic spectrum management problem within a multi-user communication system with K users and N available tones. In this problem a common utility function is optimized. In particular, so called min-rate, harmonic mean and geometric mean utility functions are considered. The complexity of the optimization problems with … Read more

Sequencing and Scheduling in Coil Coating with Shuttles

We consider a complex planning problem in integrated steel production. A sequence of coils of sheet metal needs to be color coated in consecutive stages. Di erent coil geometries and changes of coatings may necessitate time-consuming setup work. In most coating stages one can choose between two parallel color tanks in order to reduce setup times. … Read more