|
|
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 |
|
|