Solving Min-Max Problems with Applications to Games

@misc{citeulike:2302025, abstract = {We refine existing general network optimization techniques, give new characterizations for the class of problems to which they can be applied, and show that they can also be used to solve various two-player games in almost linear time. Among these is a new variant of the network interdiction problem, where the interdictor wants to destroy high-capacity paths from the source to the destination using a vertex-wise limited budget of arc removals. We also show that replacing the limit average in mean payoff games by the maximum weight results in a class of games amenable to these techniques.}, author = {Andersson, Daniel }, citeulike-article-id = {2302025}, eprint = {0801.4130}, keywords = {min-max-problem}, month = {Jan}, posted-at = {2008-01-29 12:48:30}, priority = {2}, title = {Solving Min-Max Problems with Applications to Games}, url = {http://arxiv.org/abs/0801.4130}, year = {2008} }

TY - ELEC ID - citeulike:2302025 L3 - citeulike-article-id:2302025 TI - Solving Min-Max Problems with Applications to Games N2 - We refine existing general network optimization techniques, give new characterizations for the class of problems to which they can be applied, and show that they can also be used to solve various two-player games in almost linear time. Among these is a new variant of the network interdiction problem, where the interdictor wants to destroy high-capacity paths from the source to the destination using a vertex-wise limited budget of arc removals. We also show that replacing the limit average in mean payoff games by the maximum weight results in a class of games amenable to these techniques. KW - min-max-problem AU - Andersson, Daniel PY - 2008/Jan/27/ UR - http://arxiv.org/abs/0801.4130 ER -