Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-16T18:00:46.335Z Has data issue: false hasContentIssue false

Feasible Schedules for Rotating Transmissions

Published online by Cambridge University Press:  31 July 2006

NOGA ALON
Affiliation:
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel and Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: [email protected])

Abstract

Motivated by a scheduling problem that arises in the study of optical networks, we prove the following result, which is a variation of a conjecture of Haxell, Wilfong and Winkler.

Let $k,n$ be two positive integers, let $w_{sj}, 1 \leq s \leq n, 1 \leq j \leq k$ be nonnegative reals satisfying $\sum_{j=1}^k w_{sj}< 1/n$ for every $1 \leq s \leq n$ and let $d_{sj}$ be arbitrary nonnegative reals. Then there are real numbers $x_1, x_2, {\ldots}\,,x_n$ such that for every $j$, $1 \leq j \leq k$, the $n$ cyclic closed intervals $I_s^{(j)}=[x_s+d_{sj},x_s+d_{sj}+w_{sj}]$, $(1 \leq s \leq n)$, where the endpoints are reduced modulo 1, are pairwise disjoint on the unit circle.

The proof is based on some properties of multivariate polynomials and on the validity of the Dyson conjecture.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)