4 papers
Anomaly Detection and Correction in Large Labeled Bipartite Graphs
R. W. R. Darling, Mark L. Velednitsky
Binary classification problems can be naturally modeled as bipartite graphs, where we attempt to classify right nodes based on their left adjacencies. We consider the case of label…
Solving -Stable Instances of k-Terminal Cut with Isolating Cuts
Mark Velednitsky
The k-Terminal Cut problem, also known as the Multiway Cut problem, is defined on an edge-weighted graph with distinct vertices called "terminals." The goal is to remove a mini…
Short Combinatorial Proof that the DFJ Polytope is contained in the MTZ Polytope for the Asymmetric Traveling Salesman Problem
Mark Velednitsky
For the Asymmetric Traveling Salesman Problem (ATSP), it is known that the Dantzig-Fulkerson-Johnson (DFJ) polytope is contained in the Miller-Tucker-Zemlin (MTZ) polytope. The ana…
DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals
Minjun Chang, Dorit S. Hochbaum, Quico Spaen +1
This work presents an optimally-competitive algorithm for the problem of maximum weighted online perfect bipartite matching with i.i.d. arrivals. In this problem, we are given a kn…