Zobrazeno 1 - 10
of 146
pro vyhledávání: '"Sanità, Laura"'
Flexible network design deals with building a network that guarantees some connectivity requirements between its vertices, even when some of its elements (like vertices or edges) fail. In particular, the set of edges (resp. vertices) of a given graph
Externí odkaz:
http://arxiv.org/abs/2404.08972
The circuits of a polyhedron are a superset of its edge directions. Circuit walks, a sequence of steps along circuits, generalize edge walks and are "short" if they have few steps or small total length. Both interpretations of short are relevant to t
Externí odkaz:
http://arxiv.org/abs/2402.01066
Autor:
Kukharenko, Kirill, Sanità, Laura
The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point al
Externí odkaz:
http://arxiv.org/abs/2311.15799
Autor:
Sanità, Laura, Verberk, Lucy
Capacitated network bargaining games are popular combinatorial games that involve the structure of matchings in graphs. We show that it is always possible to stabilize unit-weight instances of this problem (that is, ensure that they admit a stable ou
Externí odkaz:
http://arxiv.org/abs/2311.09904
This paper addresses a graph optimization problem, called the Witness Tree problem, which seeks a spanning tree of a graph minimizing a certain non-linear objective function. This problem is of interest because it plays a crucial role in the analysis
Externí odkaz:
http://arxiv.org/abs/2211.12431
An edge-weighted, vertex-capacitated graph G is called stable if the value of a maximum-weight capacity-matching equals the value of a maximum-weight fractional capacity-matching. Stable graphs play a key role in characterizing the existence of stabl
Externí odkaz:
http://arxiv.org/abs/2211.12179
We present new pivot rules for the Simplex method for LPs over 0/1 polytopes. We show that the number of non-degenerate steps taken using these rules is strongly polynomial and even linear in the dimension or in the number of variables. Our bounds on
Externí odkaz:
http://arxiv.org/abs/2111.14050
Many network design problems deal with the design of low-cost networks that are resilient to the failure of their elements, such as nodes or links. One such problem is Connectivity Augmentation, where the goal is to cheaply increase the connectivity
Externí odkaz:
http://arxiv.org/abs/2108.02041
Autor:
Bauckholt, Felix, Sanità, Laura
The stable marriage problem with ties is a well-studied and interesting problem in game theory. We are given a set of men and a set of women. Each individual has a preference ordering on the opposite group, which can possibly contain ties. A stable m
Externí odkaz:
http://arxiv.org/abs/2003.10277