OR Seminar - Emiliano Lancini

Emiliano Lancini (Université Paris Dauphine).
Invited by Daniele Catanzaro

will give a presentation on :

Sequential picking games against greedy on Matroids

Abstract : 

Given a hypergraph on a set of n ordered vertices, we define an independent set X to be feasible, if X is a possible outcome for a player in a sequential picking game, against a greedyadversary, where no hyperedge can be contained in the union of both outcomes. We prove that testing feasibilty is NP-complete, even if the hypergaph is a graph, but it becomes polynomial for matroid hypergraphs, that is, when the hyperedges are the circuits of some matroid. We prove that optimizing a linear function over feasible sets is NP-hard for matroid hypergraphs, even for graphic matroids, but it becomes polynomial for laminar matroids.

  Emiliano Lancini