Dorit S. Hochbaum : A general purpose technique for approximation algorithms

Dorit S. Hochbaum
Department of IE&OR Etcheverry Hall, University of California, Berkeley Ca.
hochbaum@ieor.berkeley.edu

The class of integer programs where each constraint has up to two variables, IP2, is shown to have 2-approximation algorithms that are derived in polynomial time by solving a minimum cut problem on an associated graph. Prominent NP-hard problems that can be formulated as IP2 problems include: Vertex Cover, minimum satisfiability, min 2-SAT, the max clique represented as a min node deletion problem, several submodular minimization problem (also on multi-sets) and others.
Interesting applications in which the IP2 formulation has monotone constraints (the coefficients of the two variables have opposite signs) are solved in integers in polynomial time. Applications that have been discovered to be polynomial time solvable under this framework include data mining, image segmentation, certain Rayleigh ratio problems and other ratio problems all of which are polynomial time solvable with an extension of the techniques described.
The results extend to formulations with three variables per inequality where a third variable can appear in one constraint only. These problems have a polynomial time algorithm to generate super optimal half integral solution which, if they can be rounded to a feasible solution, generate 2-approximate solutions. If the constraints are monotone, then optimal solutions are found in polynomial time.

Dorit S. Hochbaum is a full professor and Chancellor chair at UC Berkeley's department of Industrial Engineering and Operations Research (IEOR). Her research interests are in the areas of design and analysis of computer algorithms, approximation algorithms and discrete and continuous optimization. Her recent work focuses on efficient techniques related to network flows with novel applications in ranking, pattern recognition, data mining and image segmentation problems.
Professor Hochbaum is the author of over 150 papers that appeared in the Operations Research, Management Science and Theoretical Computer Science literature. Prof. Dorit S. Hochbaum was awarded an honorary doctorate of sciences by the University of Copenhagen recognizing Hochbaum's ground-breaking achievements and leadership in optimization in general and in the field of approximation algorithms for intractable problems in particular. Hochbaum was awarded the title of INFORMS fellow for the extent of her contributions to Operations Research, Management Science and design of algorithms. She is the winner of the 2011 INFORMS Computing Society prize for best paper dealing with the Operations Research/Computer Science interface. Professor Hochbaum was named fellow of the Society of Industrial and Applied Mathematics (SIAM) in 2014.