Dorit S. Hochbaum
#31,129
Most Influential Person Now
Professor of business administration, industrial engineering and operations research at the University of California, Berkeley.
Dorit S. Hochbaum's AcademicInfluence.com Rankings
Dorit S. Hochbaumengineering Degrees
Engineering
#1742
World Rank
#2508
Historical Rank
Industrial Engineering
#7
World Rank
#8
Historical Rank
Applied Physics
#684
World Rank
#706
Historical Rank
Download Badge
Engineering
Dorit S. Hochbaum's Degrees
- PhD Operations Research Stanford University
- Masters Operations Research Stanford University
- Bachelors Mathematics Tel Aviv University
Similar Degrees You Can Earn
Why Is Dorit S. Hochbaum Influential?
(Suggest an Edit or Addition)According to Wikipedia, Dorit S. Hochbaum is a professor of industrial engineering and operations research at the University of California, Berkeley. She is known for her work on approximation algorithms, particularly for facility location, covering and packing problems, and scheduling, and on flow and cut algorithms, Markov random fields, image segmentation and clustering.
Dorit S. Hochbaum's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- Approximation Algorithms for NP-Hard Problems (1996) (2106)
- A Best Possible Heuristic for the k-Center Problem (1985) (968)
- Approximation schemes for covering and packing problems in image processing and VLSI (1985) (732)
- Using dual approximation algorithms for scheduling problems: Theoretical and practical results (1985) (730)
- Approximation Algorithms for the Set Covering and Vertex Cover Problems (1982) (491)
- A unified approach to approximation algorithms for bottleneck problems (1986) (363)
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach (1988) (334)
- Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems (1996) (288)
- Heuristics for the fixed cost median problem (1982) (287)
- Efficient bounds for the stable set, vertex cover and set packing problems (1983) (284)
- An efficient algorithm for Co-segmentation (2009) (258)
- Convex separable optimization is not much harder than linear optimization (1990) (234)
- A Polynomial Algorithm for the k-cut Problem for Fixed k (1994) (222)
- The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem (2008) (205)
- Polynomial algorithm for the k-cut problem (1988) (201)
- Simple and Fast Algorithms for Linear and Integer Programs With Two Variables per Inequality (1994) (186)
- Analysis of the greedy approach in problems of maximum k‐coverage (1998) (186)
- An efficient algorithm for image segmentation, Markov random fields and related problems (2001) (175)
- Methodologies and Algorithms for Group-Rankings Decision (2006) (168)
- Performance Analysis and Best Implementations of Old and New Algorithms for the Open-Pit Mining Problem (2000) (161)
- Database Location in Computer Networks (1980) (138)
- Capacity Acquisition, Subcontracting, and Lot Sizing (2001) (138)
- Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime (1997) (137)
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality (1993) (126)
- Approximating Clique and Biclique Problems (1998) (118)
- Solving the Convex Cost Integer Dual Network Flow Problem (1999) (116)
- Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems (1994) (109)
- A nonlinear Knapsack problem (1995) (108)
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints (1995) (104)
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs (1998) (103)
- A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem (2009) (101)
- Using dual approximation algorithms for scheduling problems: practical and theoretical results (1987) (96)
- A new—old algorithm for minimum‐cut and maximum‐flow in closure graphs (2001) (96)
- Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem (1991) (92)
- Analysis of a flow problem with fixed charges (1989) (91)
- Complexity and algorithms for nonlinear optimization problems (2007) (90)
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine (1999) (85)
- A fast approximation algorithm for the multicovering problem (1986) (78)
- Scheduling with batching: minimizing the weighted number of tardy jobs (1994) (77)
- Various notions of approximations: good, better, best, and more (1996) (75)
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations (2002) (75)
- Polynomial Time Algorithms for Ratio Regions and a Variant of Normalized Cut (2010) (68)
- A best possible approximation algorithm for the k--center problem (1985) (67)
- Due Date Quotation Models and Algorithms (2004) (65)
- The SONET edge‐partition problem (2003) (63)
- Probabilistic Analysis of the Planar k-Median Problem (1980) (60)
- Fast Approximation Algorithms for a Nonconvex Covering Problem (1987) (59)
- Efficient Algorithms for the Inverse Spanning-Tree Problem (2003) (54)
- Minimizing a Convex Cost Closure Set (2000) (53)
- The t-Vertex Cover Problem: Extending the Half Integrality Framework with Budget Constraints (1998) (53)
- A Better than "Best Possible" Algorithm to Edge Color Multigraphs (1986) (52)
- An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane (1994) (51)
- A Modified Greedy Heuristic for the Set Covering Problem with Improved Worst Case Bound (1993) (48)
- Minimizing the number of tardy job units under release time constraints (1990) (48)
- Nuclear threat detection with mobile distributed sensor networks (2011) (47)
- An algorithm for the detection and construction of Monge sequences (1989) (44)
- A Cut-Based Algorithm for the Nonlinear Dual of the Minimum Cost Network Flow Problem (2004) (44)
- Forest Harvesting and Minimum Cuts: A New Approach to Handling Spatial Constraints (1997) (43)
- An optimal test compression procedure for combinational circuits (1996) (42)
- Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms (2006) (41)
- 50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today (2004) (40)
- A Polynomial Approximation Scheme for Machine Scheduling on Uniform Processors: Using the Dual Approximation Approach (1986) (40)
- Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources (1994) (40)
- When are NP-hard location problems easy? (1984) (37)
- HNCcorr: A Novel Combinatorial Approach for Cell Identification in Calcium-Imaging Movies (2017) (33)
- An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem (1985) (32)
- LOCATING CENTERS IN A DYNAMICALLY CHANGING NETWORK, AND RELATED PROBLEMS. (1998) (31)
- The Bounded Cycle-Cover Problem (2001) (31)
- The Pseudoflow Algorithm and the Pseudoflow-Based Simplex for the Maximum Flow Problem (1998) (31)
- A comparative study of the leading machine learning techniques and two new optimization algorithms (2019) (30)
- Complexity and algorithms for convex network optimization and other nonlinear problems (2005) (30)
- Baseball, Optimization, and the World Wide Web (2002) (28)
- A polynomial algorithm for an integer quadratic non-separable transportation problem (1992) (27)
- A Polynomial Time Algorithm for Rayleigh Ratio on Discrete Variables: Replacing Spectral Techniques for Expander Ratio, Normalized Cut, and Cheeger Constant (2013) (27)
- Monotonizing linear programs with up to two nonzeroes per column (2004) (26)
- Security routing games with multivehicle Chinese postman problem (2014) (25)
- The multicovering problem (1992) (24)
- The Supervised Normalized Cut Method for Detecting, Classifying, and Identifying Special Nuclear Materials (2014) (24)
- Sparse computation for large-scale data mining (2014) (24)
- Technical Note - Solving Linear Cost Dynamic Lot-Sizing Problems in O(n log n) Time (2008) (23)
- Steinhaus's geometric location problem for random samples in the plane (1982) (23)
- Ranking Sports Teams and the Inverse Equal Paths Problem (2006) (22)
- k-edge Subgraph Problems (1997) (21)
- Simplifications and speedups of the pseudoflow algorithm (2012) (21)
- Approximation Algorithms for the k-Clique Covering Problem (1996) (19)
- Optimizing over Consecutive 1's and Circular 1's Constraints (2006) (19)
- Evaluating performance of image segmentation criteria and techniques (2013) (18)
- On the Complexity of the Production-Transportation Problem (1996) (18)
- Approximation Schemes for Covering and Packing Problems in Robotics and VLSI (1984) (18)
- Rating Customers According to Their Promptness to Adopt New Products (2011) (18)
- Network-based approaches elucidate differences within APOBEC and clock-like signatures in breast cancer (2019) (17)
- Instant Recognition of Half Integrality and 2-Approximations (1998) (17)
- An O(n log2 n) Algorithm for the Maximum Weighted Tardiness Problem (1989) (16)
- Competitive Analysis of Minimum-Cut Maximum Flow Algorithms in Vision Problems (2010) (16)
- The separation, and separation-deviation methodology for group decision making and aggregate Ranking (2010) (15)
- Easy Solutions for the K–Center Problem or the Dominating Set Problem on Random Graphs (1985) (15)
- Powers of graphs: A powerful approximation technique for bottleneck problems (1984) (15)
- Multi-Label Markov Random Fields as an Efficient and Effective Tool for Image Segmentation, Total Variations and Regularization (2013) (14)
- A competitive study of the pseudoflow algorithm for the minimum s–t cut problem in vision applications (2016) (14)
- A Fast Perfect-Matching Algorithm in Random Graphs (1990) (13)
- Efficient algorithms to discover alterations with complementary functional association in cancer (2018) (13)
- A Faster Algorithm Solving a Generalization of Isotonic Median Regression and a Class of Fused Lasso Problems (2017) (12)
- Generalized p-Center problems: Complexity results and approximation algorithms (1997) (12)
- On the partitioning of graphs and hypergraphs (1987) (12)
- A packing problem you can almost solve by sitting on your suitcase (1986) (12)
- Ranking of multidimensional drug profiling data by fractional-adjusted bi-partitional scores (2012) (12)
- AnO(logk)-approximation algorithm for thek minimum spanning tree problem in the plane (1997) (12)
- Complexity of some inverse shortest path lengths problems (2010) (11)
- The bottleneck graph partition problem (1996) (11)
- Country credit-risk rating aggregation via the separation-deviation model (2008) (11)
- Minimax problems with bitonic matrices (2002) (11)
- Why Should Biconnected Components be Identified First (1993) (11)
- A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources (1999) (10)
- Algorithms and complexity of range clustering (2018) (10)
- An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs (1992) (9)
- A polynomial time repeated cuts algorithm for the time cost tradeoff problem: The linear and convex crashing cost deadline problem (2016) (9)
- On the Fractional Solution to the Set Covering Problem (1983) (9)
- On Hardness of Multiflow Transmission in Delay Constrained Cooperative Wireless Networks (2011) (8)
- Adjacency-Clustering and Its Application for Yield Prediction in Integrated Circuit Manufacturing (2018) (8)
- Scheduling with Batching: Two Job Types (1997) (8)
- Approximating a generalization of MAX 2SAT and MIN 2SAT (2000) (8)
- Sparse-Reduced Computation - Enabling Mining of Massively-large Data Sets (2016) (8)
- Covering the edges of bipartite graphs using K2, 2 graphs (2007) (8)
- A focused issue on supply chain management (2002) (8)
- Asymptotically Optimal Linear Algorithm for the Minimum k-Cut in a Random Graph (1990) (8)
- The k-Allocation Problem and Its Variants (2006) (8)
- Polynomial and Strongly Polynomial Algorithms for Convex Network Optimization (1993) (8)
- Experimental Analysis of the MRF Algorithm for Segmentation of Noisy Medical Images (2011) (7)
- The inequality-satisfiability problem (2008) (7)
- Production cost functions and demand uncertainty effects in price-only contracts (2015) (7)
- Dynamic evolution of economically preferred facilities (2009) (7)
- An Efficient and Effective Tool for Image Segmentation, Total Variations and Regularization (2011) (7)
- Approximation Algorithms for a Minimization Variant of the Order-Preserving Submatrices and for Biclustering Problems (2013) (6)
- A Graph-Theoretic Approach for Spatial Filtering and Its Impact on Mixed-Type Spatial Pattern Recognition in Wafer Bin Maps (2020) (6)
- Path Costs in Evolutionary Tree Reconstruction (1997) (6)
- Identifying Drug Sensitivity Subnetworks with NETPHIX (2019) (6)
- Polynomial time algorithms for bi-criteria, multi-objective and ratio problems in clustering and imaging. Part I: Normalized cut and ratio regions (2008) (5)
- High-performance geometric algorithms for sparse computation in big data analytics (2017) (5)
- Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (1998) (5)
- Machine Learning and Data Mining with Combinatorial Optimization Algorithms (2018) (5)
- Approximation Algorithms for Network Design Problems on Bounded Subsets (1996) (5)
- Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques (1999) (5)
- Submodular problems - approximations and algorithms (2010) (5)
- Instant recognition of polynominal time solvability, half integrality and 2-approximations (2000) (5)
- How to allocate review tasks for robust ranking (2010) (4)
- Faster pseudoflow-based algorithms for the bipartite matching and the closure problems (2004) (4)
- Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem (1986) (4)
- Network Flow Methods for the Minimum Covariates Imbalance Problem (2020) (4)
- The empirical performance of a polynomial algorithm for constrained nonlinear optimization (1993) (4)
- Can a System of Linear Diophantine Equations be Solved in Strongly Polynomial Time ? (1994) (4)
- Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm (2011) (4)
- OR Practice - Lagrangian Relaxation for Testing Infeasibility in VLSI Routing (1986) (4)
- The Max-Cut Decision Tree: Improving on the Accuracy and Running Time of Decision Trees (2020) (3)
- Complexity and approximations for submodular minimization problems on two variables per inequality constraints (2018) (3)
- On the Impossibility of Strongly Polynomial Algorithms for the Allocation Problem and its Extensions (1990) (3)
- Range contracts: Risk sharing and beyond (2015) (3)
- Isolation branching: a branch and bound algorithm for the k-terminal cut problem (2020) (3)
- A new approach for real-time target tracking in videos (2013) (3)
- Replacing spectral techniques for expander ratio, normalized cut and conductance by combinatorial flow algorithms (2010) (3)
- A unified approach for a 1D generalized total variation problem (2021) (3)
- Real-time robust target tracking in videos via graph-cuts (2013) (3)
- Efficient deployment of mobile detectors for security applications (2015) (3)
- Approximation algorithms for connected maximum coverage problem for the discovery of mutated driver pathways in cancer (2020) (2)
- A Better Decision Tree: The Max-Cut Decision Tree with Modified PCA Improves Accuracy and Running Time (2022) (2)
- An Efficient and Effective Image Segmentation Interactive Tool (2009) (2)
- Detecting Aberrant Linking Behavior in Directed Networks (2019) (2)
- A k-Means Algorithm for Clustering with Soft Must-link and Cannot-link Constraints (2022) (2)
- The multi‐integer set cover and the facility terminal cover problem (2009) (2)
- An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals (2019) (2)
- Min cost flow on unit capacity networks and convex cost K-flow are as easy as the assignment problem with All-Min-Cuts algorithm (2016) (2)
- IEOR 269, Spring 2010 Integer Programming and Combinatorial Optimization (2010) (2)
- A Polynomial-Time Algorithm for (2-2/k)-stable Instances of the k-terminal cut Problem (2018) (2)
- The Complexity of Nonlinear Separable Optimization (1989) (1)
- Optimization algorithms for survivable network design problems (1999) (1)
- Lecture Notes for IEOR 266 : Graph Algorithms and Network Flows Professor (2011) (1)
- Implementations of the pseudoflow algorithm for maximum flow, bipartite matching, flows in unit capacity networks, and parametric maximum flow (2007) (1)
- The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem (2019) (1)
- A New and Fast Approach to Very Large Scale Integrated Sequential Circuit Test Generation (1997) (1)
- HNCcorr: combinatorial optimization for neuron identification (2020) (1)
- Multiflow Transmission in Delay Constrained Cooperative Wireless Networks (2012) (1)
- The Linzertorte problem, or a unified approach to painting, baking and weaving (1986) (1)
- The Concept of Best Probability in the Analysis of Approximation Algorithms (1991) (1)
- DISPATCH: An Optimal Algorithm for Online Perfect Bipartite Matching with i.i.d. Arrivals (2018) (1)
- IEOR 266, Fall 2003 Graph Algorithms and Network Flows (1)
- An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals (2018) (1)
- Adjacency-Clustering for Identifying Defect Patterns and Yield Prediction in Integrated Circuit Manufacturing (2019) (1)
- Network-based approaches elucidate differences within APOBEC and clock-like signatures in breast cancer (2020) (0)
- Networking over Next-generation Satellite Systems Committee in Charge: Networking over Next-generation Satellite Systems Abstract Networking over Next-generation Satellite Systems Contents (1999) (0)
- To appear in : Approximation Algorithms (2007) (0)
- Applications and efficient algorithms for integer programming problems on monotone constraints (2020) (0)
- Principles of Systems Biology, No. 31. (2018) (0)
- A Data-Mining Linear Programming Model to Predict Cyclic Metal Fatigue Parameters (2008) (0)
- Joint aggregation of cardinal and ordinal evaluations with an application to a student paper competition (2021) (0)
- Algorithms and Complexity for Variants of Covariates Fine Balance (2020) (0)
- Capacity acquisition and subcontracting (2000) (0)
- A competitive study of the pseudoflow algorithm for the minimum s–t cut problem in vision applications (2013) (0)
- Benchmark Problems for Totally Unimodular Set System Auction (2011) (0)
- A Fully Polynomial Time Approximation Scheme for the Replenishment Storage Problem (2020) (0)
- Complexity, algorithms and applications of the integer network flow with fractional supplies problem (2021) (0)
- Fast Algorithms for the Capacitated Vehicle Routing Problem using Machine Learning Selection of Algorithm's Parameters (2022) (0)
- HNCcorr: combinatorial optimization for neuron identification (2019) (0)
- The Separation , and Separation-Deviation Methodology (2010) (0)
- 0 a Generic R-approximation Algorithm (0)
- IEOR 266 , Fall 2008 Graph Algorithms and Network Flows Professor (2009) (0)
- Obituary for Professor Emeritus Jakob Kraurp (2023) (0)
- Efficient algorithms for the ultimate pit limit problem (1996) (0)
- ONTHE COMPLEXITY OF THE PRODUCTION-TRANSPORTATIONPROBLEM* (1996) (0)
- Erratum: A Faster Algorithm Solving a Generalization of Isotonic Median Regression and a Class of Fused Lasso Problems (2020) (0)
- PCCC: The Pairwise-Confidence-Constraints-Clustering Algorithm (2022) (0)
- Spatial Pattern Recognition with Adjacency-Clustering: Improved Diagnostics for Semiconductor Wafer Bin Maps (2020) (0)
- Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques (1999) (0)
- Weighted matching with pair restrictions (2017) (0)
- Weighted matching with pair restrictions (2018) (0)
- Aprimal{dualinterpretationoftwo2-approximationalgorithms forthefeedbackvertexsetprobleminundirectedgraphs (1998) (0)
This paper list is powered by the following services:
Other Resources About Dorit S. Hochbaum
What Schools Are Affiliated With Dorit S. Hochbaum?
Dorit S. Hochbaum is affiliated with the following schools:
