Weak epsilon-nets for points on a hypersphere

Bradford, Phillip G.; Capoyleas, Vasilis

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Report

Weak epsilon-nets for points on a hypersphere

MPS-Authors

Bradford, Phillip G.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Capoyleas, Vasilis
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

MPI-I-95-1-029.pdf
(Any fulltext), 5MB

Supplementary Material (public)

There is no public supplementary material available

Citation

Bradford, P. G., & Capoyleas, V.(1995). Weak epsilon-nets for points on a hypersphere (MPI-I-1995-1-029). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-A1CF-F

Abstract

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.