×

zbMATH — the first resource for mathematics

A feasible direction algorithm without line search for solving max-bisection problems. (English) Zbl 1086.65062
Given an edge valued undirected graph, the max-bisection problem is the partition the node set such that the sum of edge values of edges which initiate in a partition set and ends in the other set is maximum. The max-bisection problem is NP-hard.
In order to solve the problem the authors convert the max-bisection problem into a continuous nonlinear programming problem which solution gives an upper bound on the optimal value of the max-bisection problem. From that solution a greedy strategy is used to generate a satisfactory approximate solution of max-bisection problem.
A feasible direction method without line searches is proposed to solve the continuous nonlinear programming problem and the convergence of the algorithm to a Karush-Kuhn-Tucker (KKT) point is proved. The numerical experiments show that the proposed method is robust and mainly because it does not uses line search, it is very efficient.

MSC:
65K05 Numerical mathematical programming methods
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
68R05 Combinatorics in computer science
68R10 Graph theory (including graph drawing) in computer science
05C35 Extremal problems in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite