home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15188 < prev    next >
Encoding:
Internet Message Format  |  1992-11-18  |  1.5 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!darwin.sura.net!zaphod.mps.ohio-state.edu!rpi!crdgw1!rdsunx.crd.ge.com!barbados!ramesh
  2. From: ramesh@barbados.crd.ge.com (Rajaram  Ramesh)
  3. Newsgroups: sci.math
  4. Subject: Help needed (Problem in integer programming?)
  5. Message-ID: <1992Nov18.184914.13989@crd.ge.com>
  6. Date: 18 Nov 92 18:49:14 GMT
  7. Sender: usenet@crd.ge.com (Required for NNTP)
  8. Organization: GE Corp. Research & Development, Schenectady, NY
  9. Lines: 40
  10. Nntp-Posting-Host: barbados.crd.ge.com
  11.  
  12.  
  13. I have come across a problem in my research which probably involves 
  14. integer programming. I am looking for any insight into how to go about
  15. tackling this problem.
  16.  
  17. Given a sequence f(n), n=0,...,M-1.
  18. Given:
  19. 1. f(0)=0;
  20. 2. f(k)=f(M-k), k >0, k<M
  21. 3. f(n) is a positive integer for n > 0.
  22. 4. an integer L < M
  23. If it is of any help, f(M/2)=M/2 and f(k) < M/2 for all other k.
  24.  
  25. I wish to find a subset of indices k_1, k_2, ...  k_L, 
  26. that
  27. minimizes the double summation
  28.  
  29. sum_{l=1}^L sum_{m=1}^L f((k_l - k_m) mod M)
  30.  
  31. ,i.e.,
  32.  
  33. f((k_1 - k_1) mod M) + f((k_1 - k_2)mod M) +... + f((k_1 - k_L) mod M) +
  34. f((k_2 - k_1) mod M) + f((k_2 - k_2)mod M) +... + f((k_2 - k_L) mod M) +
  35. .
  36. .
  37. f((k_L - k_1) mod M) + f((k_L - k_2)mod M) +... + f((k_L - k_L) mod M) 
  38.  
  39.  
  40.  
  41. I do not have to necessarily find the optimum solution, 
  42. good sub-optimal solutions are okay.
  43.  
  44.  
  45. On the surface, it looks as if a complete search has to be done. If
  46. anyone knows of a trick to avoid this, I'd appreciate it.
  47.  
  48. Thanks.
  49.  
  50. Ramesh.
  51. ramesh@crd.ge.com
  52.