Design and Performance of Parallel and Distributed Approximation Algorithms for Maxcut
Authors:
- Steven HomerSHSteven Homer
- Marcus PeinadoMPMarcus Peinado
Open Access
- 1 October 1997
- journal article
- Published by Elsevier in Journal of Parallel and Distributed Computing
- Vol. 46 (1) , 48-61
Abstract
No abstract availableThis publication has 15 references indexed in Scilit:
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- A geometric approach to betweennessLecture Notes in Computer Science, 1995
- The performance of an eigenvalue bound on the max-cut problem in some classes of graphsDiscrete Mathematics, 1993
- An O(n 3 L) potential reduction algorithm for linear programmingMathematical Programming, 1991
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph PartitioningOperations Research, 1989
- Communication efficient basic linear algebra computations on hypercube architecturesJournal of Parallel and Distributed Computing, 1987
- Efficient Algorithms for Layer Assignment ProblemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- A graph-theoretic via minimization algorithm for two-layer printed circuit boardsIEEE Transactions on Circuits and Systems, 1983
- P-Complete Approximation ProblemsJournal of the ACM, 1976