Conferences

Parametric Multiroute Flow and Its Application to Robust Network with k Edge Failures — Abstract
Jean-François Baffier, Vorapong Suppakitpaisarn, Hidefumi Hiraishi, Hiroshi Imai
In this work, we investigate properties of the function taking the real value $h$ to the max $h$-route flow value, and apply the result to solve robust network flow problems. We show that the function is piecewise hyperbolic, and modify a parametric optimization technique, the ES algorithm, to find this function. The running time of the algorithm is $O(lambda mn)$, when $lambda$ is a source-sink edge connectivity of our network, $m$ is the number of links, and $n$ is the number of nodes. We can use the result from that algorithm to solve two max-flow problems against $k$ edge failures, referred to as max-MLA-robust flow and max-MLA-reliable flow. When $h$ is optimally chosen from the function, we show that the max-$h$-route flow is an exact solution of both problems for graphs in a specific class. Our numerical experiments show that $98%$ of random graphs generated in the experiment are in that specific class. Given a parametric edge $e$, we also show that the function taking the capacity of $e$ to the max-$h$-route flow value is linear piecewise. Hence we can apply our modified ES algorithm to find that function in $O(h^2mn)$.

Hide abstract

A (k + 1)-Approximation Robust Network Flow Algorithm and a Tighter Heuristic Method Using Iterative Multiroute Flow — Abstract
Jean-François Baffier, Vorapong Suppakitpaisarn
We consider two variants of a max-flow problem against $k$ edge failures, each of which can be both approximated by a multiroute flow algorithm. The maximum $k$-robust flow problem is to find the minimum max-flow value among $mchoose k$ networks that can be obtained by deleting each set of $k$ edges. The maximum $k$-balanced flow problem is to find a max-flow of the network such that the flow value is maximum against any set of $k$ edge failures, when deleting the corresponding flow to those $k$ edges in the original flow. We prove $C_M leqslant C_M',leqslant C_B leqslant C_R leqslant (k + 1)cdot C_M$, where $C_M$ is the max-$(k+1)$-route flow value, $C_M'$ is the effectiveness of the max-$(k+1)$-route flow after $k$ attacks, $C_B$ is the max-$k$-balanced flow value, and $C_R$ is the max-$k$-robust flow value. Also, we develop a polynomial-time heuristic algorithm for both cases, called the iterative multiroute flow. Our experimental results show that the average improvement made by our heuristic method can be up to $10%$ better than the multiroute flow algorithm. Compared to the optimal max-$k$-robust flow solutions -- obtained by a brute-force algorithm -- there is an average gap of $2%$ at most.

Hide abstract

A bounds-driven analysis of "Skull and Roses" cards game — Abstract
Alonso Gragera, Jean-François Baffier, Vorapong Suppakitpaisarn
In this paper, we analyze the game with large number of short states named Skull & Roses from a computer science point of view. We describe the game in a formal way, and use that formulation to obtain boundaries and average value on the game length, state-space size, and the game tree size. As a result, we can imply that developing an AI strategy for Skull & Roses could be more difficult than Shogi or Go. Since the game learning curve is relatively short for human, the game could be another evidence to show differences between humans and computers in game playing strength.

Hide abstract