|
|
 |
|
Jeudi 12 Février
| Heure: |
10:30 - 12:00 |
| Lieu: |
Salle A303, bâtiment A, Université de Villetaneuse |
| Résumé: |
Properties of matroids in picking games against Greedy |
| Description: |
Emiliano Lancini Given an 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 greedy
adversary, where no hyperedge can be contained in the union of both outcomes. We prove that
testing feasibility is NP-complete, even if the hypergraph is a graph, but it becomes polynomial
(in n) for matroid hypergraphs, that is, when the hyperedges are the circuits of some matroid
(in which independence can be tested with an oracle). We prove also that optimizing a linear
function over feasible sets is NP-hard for graphs and matroid hypergraphs, even for graphic
matroids, but it becomes polynomial for laminar matroids. |
|
|
