7 papers
A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm
Philipp Baumann, Olivier Goldschmidt, Dorit S. Hochbaum +1
Anticlustering is an NP-hard combinatorial optimization problem that consists of partitioning a set of objects into equal-sized groups called anticlusters such that the objects in…
An Effective Flow-based Method for Positive-Unlabeled Learning: 2-HNC
Dorit Hochbaum, Torpong Nitayanont
In many scenarios of binary classification, only positive instances are provided in the training data, leaving the rest of the data unlabeled. This setup, known as positive-unlabel…
Fast and Optimal Incremental Parametric Procedure for the Densest Subgraph Problem: An Experimental Study
Dorit S. Hochbaum, Ayleen Irribarra-Cortés, Olivier Goldschmidt +1
The Densest Subgraph Problem (DSP) is widely used to identify community structures and patterns in networks such as bioinformatics and social networks. While solvable in polynomial…
Min cost flow on unit capacity networks and convex cost K-flow are as easy as the assignment problem with All-Min-Cuts algorithm
Dorit S. Hochbaum
We explore here surprising links between the time-cost-tradeoff problem and the minimum cost flow problem that lead to fast, strongly polynomial, algorithms for both problems. One…
Confidence HNC: A Network Flow Technique for Binary Classification with Noisy Labels
Dorit Hochbaum, Torpong Nitayanont
We consider here a classification method that balances two objectives: large similarity within the samples in the cluster, and large dissimilarity between the cluster and its compl…
A Fast and Effective Breakpoints Heuristic Algorithm for the Quadratic Knapsack Problem
Dorit S. Hochbaum, Philipp Baumann, Olivier Goldschmidt +1
The Quadratic Knapsack Problem (QKP) involves selecting a subset of elements that maximizes the sum of pairwise and singleton utilities without exceeding a given budget. The pairwi…