A feasible direction algorithm without line search for solving max-bisection problems.

*(English)*Zbl 1086.65062Given 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.

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.

Reviewer: Vincentiu Dumitru (Bucureşti)

##### 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) |