Raziskovalni matematični seminar - Arhiv
| 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
By a seminal result of Valiant, computing the permanent of (0,1)-matrices is #P-hard. In 1913 Polya asked for which (0,1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. This, eventually, lead to a polynomial time algorithm to compute the permanent of (0,1)-matrices whose associated bipartite graph excludes K_3,3 as a matching minor. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0,1)-matrices can be computed efficiently.
We identify a class of bipartite graphs strictly generalising planar bipartite graphs and K_3,3 which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude K_5,5 as a matching minor.
This is joint work with Archontia C. Giannopoulou and Dimitrios M. Thilikos.
Join Zoom Meeting Here!
Everyone is welcome and encouraged to attend.
We study the allocation of indivisible items to agents, when each agent's preferences are expressed by means of a directed acyclic graph.
An arc (a,b) in such a graph means that the respective agent prefers item a over item b.
We introduce a new measure of dissatisfaction of an agent by counting the number of non-assigned items which are approved of by the agent and for which no more preferred item is allocated to the agent.
We seek an allocation of the items to the agents in a way that minimizes the total dissatisfaction over all agents.
We study the status of computational complexity and obtain NP-hardness results as well as polynomial algorithms with respect to natural underlying graph structures.
Joint work with Nina Chiarelli, Clément Dallard, Andreas Darmann, Stefan Lendl, Martin Milanič, Ulrich Pferschy, Nevena Pivač.
Everyone is welcome and encouraged to attend!
