Dynamic platform-independent meta-algorithms for graph-partitioning
dc.contributor.advisor | Bradley, Gordon H. | |
dc.contributor.author | Schwartz, Victor Scott | |
dc.date | September 1998 | |
dc.date.accessioned | 2012-08-09T19:19:51Z | |
dc.date.available | 2012-08-09T19:19:51Z | |
dc.date.issued | 1998-09-01 | |
dc.identifier.uri | https://hdl.handle.net/10945/8279 | |
dc.description.abstract | A dynamic platform-independent solver is developed for use with network and graph algorithms of operations research. This solver allows analysts to solve a large variety of problems without writing code. Algorithms from a library can be integrated into a meta-algorithm which also provides easy monitoring of solution progress. The solver, DORS, is demonstrated by heuristically solving a graph-partitioning problem to minimize the number of nodes adjacent to other segments of the partition. The model arises from a network-upgrade project faced by the Defense Information Systems Agency (DISA), a problem with over 200 nodes and 1400 arcs. Solutions are provided on a 266 MHz Pentium II PC using Windows NT 4.0. Eight variants of the problem are solved involving modification to the objective function, constraints on the size of partition segments, and on the number of those segments. DORS (and the meta- algorithm it implements) appears to find a good solution for one of the two problem formulations for DISA, but has difficulty solving the other. Because the solver allows new algorithms to be easily added to create more powerful meta- algorithms, DORS should provide a good solution approach for both problem formulations given a more versatile library of algorithms. | en_US |
dc.description.uri | http://archive.org/details/dynamicplatformi109458279 | |
dc.format.extent | xvi, 101 p. | en_US |
dc.language.iso | en_US | |
dc.publisher | Monterey, California. Naval Postgraduate School | en_US |
dc.rights | This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States. | en_US |
dc.title | Dynamic platform-independent meta-algorithms for graph-partitioning | en_US |
dc.type | Thesis | en_US |
dc.contributor.secondreader | Wood, R. Kevin | |
dc.contributor.corporate | Naval Postgraduate School | |
dc.contributor.department | Department of Operations Research | |
dc.subject.author | Graph partitioning | en_US |
dc.subject.author | Java | en_US |
dc.description.service | Lieutenant, United States Navy | en_US |
etd.thesisdegree.name | M.S. in Operations Research | en_US |
etd.thesisdegree.level | Masters | en_US |
etd.thesisdegree.discipline | Operations Research | en_US |
etd.thesisdegree.grantor | Naval Postgraduate School | en_US |
dc.description.distributionstatement | Approved for public release; distribution is unlimited. |
Files in this item
This item appears in the following Collection(s)
-
1. Thesis and Dissertation Collection, all items
Publicly releasable NPS Theses, Dissertations, MBA Professional Reports, Joint Applied Projects, Systems Engineering Project Reports and other NPS degree-earning written works.