17 Juin - 23 Juin


Retour à la vue des calendrier
Jeudi 20 Juin
Heure: 10:30 - 11:30
Lieu: Salle A303, Université de Villetaneuse
Résumé: Partial optimality in linear ordering
Description: David Stein The linear ordering problem consists in finding a linear order < on a finite set A so as to minimize the sum of costs associated with pairs of elements a,b for which a < b. The problem is NP-hard and APX-hard. We introduce algorithms for solving the problem *partially* by deciding efficiently for some pairs (a,b) whether a