Home
 
Attendees
Conference program
Registration
Location
Hotel information
Links
 
 
Previous editions
2002


    

Session MA1 - Exposé magistral I / Tutorial I

Day Monday, May 05, 2003
Room Procter & Gamble
President Odile Marcotte

Presentations

10:30 Hypermetric Inequalities and Linear Programming Relaxations of Max Cut
  David Avis, McGill University, Computer Science, 3480 University St., Montréal, Québec, Canada, H3A 2A7

Hypermetric inequalities are a natural generalization of the triangle inequalities, and have been rediscovered many times. They find application, for example, in combinatorial optimization, geometry, physics and statistics. However, many very basic questions regarding them remain open. In this talk I will give a survey of what is known about hypermetric inequalities, and a sketch of how they are applied. In particular I will describe how they are useful in solving the problem of finding a maximum edge cut in a graph and in deciding the embeddability of point sets in space, with prescribed L1 distances. I will discuss some of the interesting open problems surrounding these beautiful inequalities.