Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-95-1-029

Weak epsilon-nets for points on a hypersphere

Bradford, Phillip G. and Capoyleas, Vasilis

MPI-I-95-1-029. October 1995, 8 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

We present algorithms for the two layer straightline crossing
minimization problem that are able to compute exact optima.
Our computational results lead us to the conclusion that there
is no need for heuristics if one layer is fixed, even though
the problem is NP-hard, and that for the general problem with
two variable layers, true optima can be computed for sparse
instances in which the smaller layer contains up to 15 nodes.
For bigger instances, the iterated barycenter method turns out
to be the method of choice among several popular heuristics
whose performance we could assess by comparing the results
to optimum solutions.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-95-1-029.pdfMPI-I-95-1-029.pdf4483 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-029
Hide details for BibTeXBibTeX
@TECHREPORT{BradfordCapoyleas95,
  AUTHOR = {Bradford, Phillip G. and Capoyleas, Vasilis},
  TITLE = {Weak epsilon-nets for points on a hypersphere},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-95-1-029},
  MONTH = {October},
  YEAR = {1995},
  ISSN = {0946-011X},
}