|
|
|
Séance TB9 - Graphes IV / Graphs IV
Jour |
mardi, le 10 mai 2005 |
Salle |
St-Hubert |
Président |
Brigitte Jaumard |
Présentations
13h30 |
Equivalence of some LP-based lower bounds for the Golomb ruler problem |
|
Brigitte Jaumard, Université de Montréal, GERAD, CRT et Informatique et recherche opérationnelle, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
Christophe Meyer, Université de Montréal, Informatique et recherche opérationnelle, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
The Golomb Ruler problem consists in finding $n$ integers such that all possible differences are distinct and such that the largest difference is minimum. We review three lower bounds based on linear programming that have been proposed in the literature for this problem, and propose a new one. We then show that these 4 lower bounds are equal. Finally we discuss some computational experience aiming at identifying the easiest lower bound to compute in practice.
|
13h55 |
On the Design of Optimum Order 2 Golomb Ruler |
|
Yannick Solari, Université de Montréal, Informatique et recherche opérationnelle, C.P. 6128, succursale Centre-ville, Montréal, Québec, Canada, H3C 3J7
Brigitte Jaumard, Université de Montréal, GERAD, CRT et Informatique et recherche opérationnelle, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
Philippe Galinier, École Polytechnique de Montréal, Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
A Golomb ruler with M marks can be defined as a set of integers so that all pairwise differences are distinct.
An order 2 Golomb ruler is a Golomb ruler such that all differences of pairwise differences are distinct as much as possible. Contruction of optimum order 2 Golomb ruler, i.e., of rulers of minimum length, is a highly combinatorial problem which has applications, e.g., in the design of convolutional self doubly orthogonal codes. We propose here a first exact algorithm, different from a pure exhaustive search, for building optimum order 2 Golomb rulers and provide optimal rulers for up to 9 marks and new rulers which improve on the previous ones for up to 20 marks.
|
14h20 |
Integer Linear Programming Formulations for the Design of DTS - Difference Triangle Sets |
|
Maurice Morel, École Polytechnique de Montréal, GERAD et Génie électrique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Brigitte Jaumard, Université de Montréal, GERAD, CRT et Informatique et recherche opérationnelle, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
Odile Marcotte, Université du Québec à Montréal, GERAD et Informatique, C.P. 8888, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3P8
We will present and discuss different integer linear programming formulations for the design of DTS - Difference Traingle Set. A (I,J)-DTS is a set of I Golomb rulers with J+1 marks each, which have no common difference.
|
|