Dorit S. Hochbaum, Professor

Contact:

Etcheverry Hall

University of California

Berkeley, CA 94720

TEL: (510) 642-4998

dhochbaum at berkeley.edu

Research Interests:

I try to be an optimizer in whatever I do, and my research interests reflect that. Some problem applications I am interested in include:

Data mining and pattern recognition with flow techniques
Image segmentation and detecting hidden features in medical images
Detecting security threats - domestic nuclear threat security (detection) - The DoNuTS project
Information technology issues in supply chain management
Manufacturing of VLSI circuit
Testing and designing circuits
Scheduling problems
Planning of mining operations
Locations of facilities
Distribution and logistics
And, baking cakes optimally

News

UC Berkeley, along with Georgia Tech, USC and other universities, was awarded $20M for the for the renewal of the AI$OPT, NSF National AI Institute for Advances in Optimization, 2026-2031.

Khachian Prize, yeyyy.

A new, very efficient, breakpoints algorithm for the quadratic Knapsack problem, based on the parametric HPF procedure. Dorit S. Hochbaum, Philipp Baumann, Olivier Goldschmidt, Yiqing Zhang. A Fast and Effective Heuristic Breakpoints Algorithm for the Quadratic Knapsack Problem. European Journal on Operational Research, 323, 425-440. (2025).

As for older news:

A new maximum diversity algorithm IEOR News.

The neuron segmentation algorithm HNCcorr is one of the leading algorithms in the Neurofinder benchmark for cell identification in calcium imaging movies. The algorithm is HNC (Hochbaum Normalized Cut), aka NC', with similarities based on distances in correlation space. This is joint work with Quico Spaen and Roberto Asin.

Algorithms with Software

Software for algorithms used and developed in my research group.

HNCcorr for neuronal cell identification in Calcium-imaging movies.
Sparse Computation to generate sparse similarities graph
A fully parametric flow/cut HPF for linear capacities
HPF Hochbaum's PseudoFlow algorithm - an implementation
Simple Parametric HPF: Version 1.0 for any parametric functions; Version 2.0 for linear parametric functions with listing of parameters
Single or multi-frame image segmentation with the flow algorithm HPF as subroutine
An efficient algorithm for co-segmentation with the flow algorithm HPF as subroutine
Incremental Parametric Cut procedure for the conductance star Problem (related to Conductance and Cheeger Constant)
Incremental Parametric Cut procedure for the Densest Subgraph Problem
An archive of no-longer-active past algorithms with Java interfaces is included in our RIOT Project site.
The algorithm for the baseball elimination problem based on the paper
Ilan Adler, Alan Erera, Dorit S. Hochbaum and Eli Olinick, "Baseball, Optimization and the World Wide Web", Interfaces 32:2 March-April 2002, pp. 12-22.
is included here: Baseball elimination

Publications

Lecture Notes

IEOR 266
Network Flows & Graph Algorithms
Updated Spring 2024

IEOR 290G
Nonlinear Complexity & Combinatorial Optimization
Updated Spring 2017

IEOR 269
Integer Programming & Combinatorial Optimization
Updated 2010