On uncrossing games for skew-supermodular functions
Hirai, Hiroshi
Original · EN
In this note, we consider the uncrossing game for a skew-supermodular function f, which is a two-player game with players, Red and Blue, and abstracts the uncrossing procedure in the cut-covering linear program associated with f. Extending the earlier results by Karzanov for {0,1}-valued skew-supermodular functions, we present an improved polynomial time strategy for Red to win, and give a strongly polynomial time uncrossing procedure for dual solutions of the cut-covering LP as its consequence. We also mention its implication on the optimality of laminar solutions.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.