home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 13060 < prev    next >
Encoding:
Internet Message Format  |  1992-10-12  |  2.4 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!spool.mu.edu!agate!doc.ic.ac.uk!uknet!mcsun!corton!irisa!irisa.fr!leverge
  2. From: leverge@irisa.fr (Herve Leverge)
  3. Newsgroups: sci.math
  4. Subject: Re: Permutation Polytopes
  5. Keywords: Extreme points
  6. Message-ID: <1992Oct12.181638.15916@irisa.fr>
  7. Date: 12 Oct 92 18:16:38 GMT
  8. References: <FRANK.92Sep18140543@ae.ae.tut.fi> <97468@bu.edu>
  9. Sender: news@irisa.fr
  10. Organization: Irisa, Rennes(FR)
  11. Lines: 72
  12.  
  13.  
  14. In article <97468@bu.edu>, mike@park.bu.edu (Michael Cohen) writes:
  15. |> 
  16. |> Treat the orderings on n letters as permutations.
  17. |> For each ordering a, define a point in n X n-1/2
  18. |> space as follows.
  19. |> 
  20. |> U_a(i,j) = 1 if i a j
  21. |> U_a(i,j) = -1 otherwise.
  22. |> 
  23. |> Consider the convex polytope U which is a convex combination of these
  24. |> extreme points.  Question:  What is the polar polyhedron.  i.e. the
  25. |> extreme points of the the of elements <l, u> <= 1. for all u in U.
  26. |>             -mike
  27. |> 
  28. |> 
  29. |> 
  30. |> -- 
  31. |> Boston University (617-353-7857) Email: mike@park.bu.edu
  32. |> Smail: Michael Cohen                     111 Cummington Street, RM 242
  33. |>        Center for Adaptive Systems        Boston, Mass 02215
  34. |>        Boston University
  35.  
  36. A slight variant of this problem has been studied extensively by
  37. G. Reinelt. For this case :
  38.  
  39. U_a(i,j)=1 if i a j
  40.         =0 otherwise
  41.          ^
  42.  
  43. You might have a look in :
  44.  
  45. @Book{Reinelt85,
  46.   author =      {{Reinelt}, Gerhard},
  47.   title =       {The Linear Ordering Problem: Algorithms and Applications},
  48.   publisher =   {Heldermann Verlag Berlin},
  49.   year =        {1985}
  50. }
  51.  
  52.  
  53. @TechReport{Reinelt91,
  54.   author =      {Gerhard Reinelt},
  55.   title =       {A Note on Small Linear Ordering Polytopes},
  56.   institution = {Institut f\"{u}r Mathematik, Universit\"{a}t Augsburg,B}
  57.   year =        {1991},
  58.   type =        {Research Report},
  59.   number =      {329},
  60.   address =     {Universit\"{a}tsstra{\ss}e 8, D-8900 Augsburg},
  61.   month =       {November}
  62. }
  63.  
  64.  
  65. @Article{Grotschel84,
  66.   author =      {{Gr\"{o}tschel}, Martin and {J\"{u}nger}, Michael and
  67.                  {Reinelt}, Gerhard},
  68.   title =       {A {C}utting {P}lane {A}lgorithm for the {L}inear {O}rdering
  69.                  {P}roblem},
  70.   journal =     {Operations Research},
  71.   year =        {1984},
  72.   volume =      {32},
  73.   number =      {6},
  74.   pages =       {1195-1220},
  75.   month =       {November-December},
  76.   OPTnote =     ""
  77. }
  78.  
  79. The corresponding polytope is only known until n=7, whose
  80. full description appears in the above report.
  81.  
  82. Hope this helps!
  83.  
  84. RV.
  85.