Preprints
We present a strongly polynomial label-correcting algorithm for solving the feasibility of linear systems with two variables per inequality (2VPI). The algorithm is based on the Newton-Dinkelbach method for fractional combinatorial optimization. We extend and strengthen previous work of Madani (2002) that showed a weakly polynomial bound for a variant of the Newton-Dinkelbach method for solving deterministic Markov decision processes (DMDPs), a special class of 2VPI linear programs. For a 2VPI system with n variables and m constraints, our algorithm runs in O(mn) iterations. Every iteration takes O(m + nlogn) time for DMDPs, and O(mn) time for general 2VPI systems.
The key technical idea is a new analysis of the Newton-Dinkelbach method exploiting gauge symmetries of the algorithm. This also leads to an acceleration of the Newton-Dinkelbach method for general fractional combinatorial optimization problems. For the special case of linear fractional combinatorial optimization, our method converges in O(mlogm) iterations, improving upon the previous best bound of O(m^2logm) by Wang et al. (2006).
Publications
Cooperative games form an important class of problems in game theory, where the goal is to distribute a value among a set of players who are allowed to cooperate by forming coalitions. An outcome of the game is given by an allocation vector that assigns a value share to each player. A crucial aspect of such games is submodularity (or convexity). Indeed, convex instances of cooperative games exhibit several nice properties, e.g. regarding the existence and computation of allocations realizing some of the most important solution concepts proposed in the literature. For this reason, a relevant question is whether one can give a polynomial time characterization of submodular instances, for prominent cooperative games that are in general non-convex. In this paper, we focus on a fundamental and widely studied cooperative game, namely the spanning tree game. An efficient recognition of submodular instances of this game was not known so far, and explicitly mentioned as an open question in the literature. We here settle this open problem by giving a polynomial-time characterization of submodular spanning tree games.
An edge-weighted graph G is called stable if the value of a maximum-weight matching equals the value of a maximum-weight fractional matching. Stable graphs play an important role in network bargaining games and cooperative matching games, because they characterize instances which admit stable outcomes. We give the first polynomial-time algorithm to find a minimum cardinality subset of vertices whose removal from G yields a stable graph, for any weighted graph G. The algorithm is combinatorial and exploits new structural properties of basic fractional matchings. In particular, one of the main ingredients of our result is the development of a polynomial-time algorithm to compute a basic maximum-weight fractional matching with the minimum number of odd cycles in its support. This generalizes a fundamental and classical result on unweighted matchings given by Balas more than 30 years ago, which we expect to prove useful beyond this particular application. In contrast, we show that the problem of finding a minimum cardinality subset of edges whose removal from a weighted graph G yields a stable graph, does not admit any constant-factor approximation algorithm, unless P = NP. In this setting, we develop an O(Δ)-approximation algorithm for the problem, where Δ is the maximum degree of a node in G.
I am a PhD student working as part of the ERC project ScaleOpt. My advisor is László Végh. Previously, I was a research assistant in the Department of Combinatorics and Optimization at the University of Waterloo, supervised by Laura Sanità.
I received my Bachelors and Masters degrees from the University of Waterloo.