Ph.D Thesis
Ph.D Student Berstein Yael Nonlinear Combinatorial Optimization Department of Industrial Engineering and Management Professor Shmuel Onn

Abstract

A combinatorial optimization problem consists of a family of subsets of a finite ground set and an objective function defined over the family; the problem is to  efficiently find a family member that maximizes or minimizes the objective function over the family. Since such problems are typically computationally very hard and often intractable, most of the literature on the subject has concentrated on problems with linear objectives.

In this thesis we consider a unified framework for combinatorial optimization with nonlinear objective functions as follows. With each element of the ground set is associated a given d-dimensional weight vector (representing its utility under d criteria). Also given is an arbitrary functional f on d-dimensional space. The weight vector of a feasible solution (namely, a member of the combinatorial family of subsets underlying the problem) is the sum of the weight vectors of its elements. The objective value of a feasible solution is the value of the functional on its weight vector. Such a nonlinear combinatorial optimization problem can be interpreted as a multi-objective combinatorial optimization problem in which the goal is to maximize (or minimize) the balancing given by the function f of the d criteria expressed by the d-dimensional weight vectors.

We develop an algorithmic methodology for nonlinear combinatorial optimization based on a combination of geometric, algebraic, and combinatorial methods, and show that it leads to efficient solution for a wide variety of nonlinear combinatorial optimization problems.

While such problems are generally hard and often intractable (for instance, even for bipartite matching with 1-dimensional weights the problem of minimizing a family of very simple convex univariate functions is NP-hard), our methodology leads to polynomial-time solution in a variety of situations, including: i. randomized algorithms for optimizing arbitrary objectives over bipartite matching and matroid intersection problems; II. deterministic algorithms for maximizing any convex function over any discrete family which can be described by a set of linear inequalities; iii. approximation algorithms for optimizing norms functions over such well described discrete families.