Source author record

Carla Michini

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Computer Science and Game Theory Discrete Mathematics math.CO math.OC

Catalog footprint

Research overview

3works

5topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Short simplex paths in lattice polytopes

The goal of this paper is to design a simplex algorithm for linear programs on lattice polytopes that traces `short' simplex paths from any given vertex to an optimal one. We consider a lattice polytope $P$ contained in $[0,k]^n$ and defined via $m$ linear inequalities. Our first contribution is a simplex algorithm that reaches an optimal vertex by tracing a path along the edges of $P$ of length in $O(n^4 k\log(nk)$ . The length of this path is independent from $m$ and it is the best possible up to a polynomial function. In fact, it is only polynomially far from the worst-case diameter, which roughly grows as a linear function in $n$ and $k$ . Motivated by the fact that most known lattice polytopes are defined via $0,\pm 1$ constraint matrices, our second contribution is an iterative algorithm which exploits the largest absolute value $α$ of the entries in the constraint matrix. We show that the length of the simplex path generated by the iterative algorithm is in $O(n^2k \log(nkα))$ . In particular, if $α$ is bounded by a polynomial in $n, k$ , then the length of the simplex path is in $O(n^2k \log(nk))$ . For both algorithms, the number of arithmetic operations needed to compute the next vertex in the path is polynomial in $n$ , $m$ and $\log k$ . If $k$ is polynomially bounded by $n$ and $m$ , the algorithm runs in strongly polynomial time.

preprint2016arXiv

Totally Unimodular Congestion Games

We investigate a new class of congestion games, called Totally Unimodular (TU) Congestion Games, where the players' strategies are binary vectors inside polyhedra defined by totally unimodular constraint matrices. Network congestion games belong to this class. In the symmetric case, when all players have the same strategy set, we design an algorithm that finds an optimal aggregated strategy and then decomposes it into the single players' strategies. This approach yields strongly polynomial-time algorithms to (i) find a pure Nash equilibrium, and (ii) compute a socially optimal state, if the delay functions are weakly convex. We also show how this technique can be extended to matroid congestion games. We introduce some combinatorial TU congestion games, where the players' strategies are matchings, vertex covers, edge covers, and stable sets of a given bipartite graph. In the asymmetric case, we show that for these games (i) it is PLS-complete to find a pure Nash equilibrium even in case of linear delay functions, and (ii) it is NP-hard to compute a socially optimal state, even in case of weakly convex delay functions.

preprint2015arXiv

On the diameter of lattice polytopes

In this paper we show that the diameter of a d-dimensional lattice polytope in [0,k]^n is at most (k - 1/2) d. This result implies that the diameter of a d-dimensional half-integral polytope is at most 3/2 d. We also show that for half-integral polytopes the latter bound is tight for any d.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.