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