| Research into two combinatorial optimization problems is presented. (1) A minimax program is a variation on a linear program obtained by changing the addition operator to the maximum operator in the constraint inequalities. The relation of minimax program to known problems is clarified, and an efficient algorithmic solution for a special case class of minimax program is described. (2) Minimum cuts in networks is an important combinatorial optimization problem that has been extensively studied. We investigated the possibility of an efficient algorithm that does not rely on the cut/path duality underlying all known deterministic, efficient algorithms for this problem. We present new formulations of the minimum cut problem, together with heuristics and algorithms based on these formulations. |
