Faster algorithms for security games on matroids

DOI10.1007/s00453-018-0466-xzbMath1422.91035OpenAlexW2809373373WikidataQ115149029 ScholiaQ115149029MaRDI QIDQ666676

Francisco Barahona, Mourad Baïou

Publication date: 11 March 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0466-x

zbMATH Keywords

two-person gamesNash-equilibriummatroid gamessecurity games

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Noncooperative games (91A10) 2-person games (91A05)

Related Items

Hitting a path: a generalization of weighted connectivity via game theory, New polyhedral and algorithmic results on greedoids

Cites Work

• Security games on matroids
• A faster strongly polynomial time algorithm for submodular function minimization
• Testing membership in matroid polyhedra
• The ellipsoid method and its consequences in combinatorial optimization
• Separating from the dominant of the spanning tree polytope
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• A rounding technique for the polymatroid membership problem
• A class of inverse dominant problems under weighted \(l_{\infty }\) norm and an improved complexity bound for Radzik's algorithm
• Design of Network Topology in an Adversarial Environment
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• A new approach to the maximum-flow problem
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• Packing Spanning Trees
• On Nonlinear Fractional Programming
• Matroids and the greedy algorithm
• Unnamed Item
• Unnamed Item