home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / 2372 < prev    next >
Encoding:
Text File  |  1992-11-08  |  1.5 KB  |  36 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!demos!hqlgu!news-server
  3. From:  jvr@or.math.lgu.spb.su (Joseph Romanovsky)
  4. Subject: Re: Elimination ordering question
  5. Reply-To: jvr@or.math.lgu.spb.su
  6. Organization: University of St-Petersburg
  7. Date: Sun, 8 Nov 1992 08:53:23 GMT
  8. Message-ID: <AA2MD_gCMA@or.math.lgu.spb.su>
  9. Lines: 24
  10. Sender: news-server@lgu.spb.su
  11.  
  12. sjha+@cs.cmu.edu (Somesh Jha) writes:
  13. >
  14. >I need some  literature on the following problem. I already have a proof that
  15. >it is NP-complete. Given a family of sets which are subsets of
  16. >{x_1,x_2, ... ,x_n}. I define what it means to eliminate x_i.
  17. >We union together all the sets which contain x_i, remove x_i from it,
  18. >and replace all these sets by the new set. Now we get a new family of
  19. >sets. The problem is to find the best elimination ordering.
  20.  
  21.    See: U.Bertele, F.Brioshi, Nonserial dynamic programming,
  22.         Academic Press, N.-Y., 1972
  23.    They used this procedure for sequential elimination of variables
  24.    in optimization problems, and considered the secondary optimization
  25.    problem of the best ordering of these eliminations.
  26.  
  27.      - Joseph Romanovsky
  28. ------------------------------------------------------------------------
  29.  Joseph Romanovsky       e-mail  <jvr@or.math.lgu.spb.su>
  30.  Professor of Operat.Res.        <jvr%or.math.lgu.spb.su@relay.eu.net>
  31.  Univ. of St-Petersburg   fax:    +7 (812) 428-6649
  32.  St.-Petersburg, Russia   phone:  +7 (812) 315-4374
  33. ------------------------------------------------------------------------
  34.  
  35.  
  36.