Zobrazeno 1 - 10
of 245
pro vyhledávání: '"Grandoni, Fabrizio"'
The $2$-Edge Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected unweighted graph, find a subgraph with the minimum number of edges which is 2-edge-connected (i.e., it remains co
Externí odkaz:
http://arxiv.org/abs/2408.07019
The Steiner tree problem is one of the most prominent problems in network design. Given an edge-weighted undirected graph and a subset of the vertices, called terminals, the task is to compute a minimum-weight tree containing all terminals (and possi
Externí odkaz:
http://arxiv.org/abs/2407.19905
In the Unsplittable Flow on a Path problem UFP, we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a subpath. Our goal is to select a maximum profit subset of tasks such tha
Externí odkaz:
http://arxiv.org/abs/2407.10138
In the maximum independent set of convex polygons problem, we are given a set of $n$ convex polygons in the plane with the objective of selecting a maximum cardinality subset of non-overlapping polygons. Here we study a special case of the problem wh
Externí odkaz:
http://arxiv.org/abs/2402.07666
In the Triangle-Free (Simple) 2-Matching problem we are given an undirected graph $G=(V,E)$. Our goal is to compute a maximum-cardinality $M\subseteq E$ satisfying the following properties: (1) at most two edges of $M$ are incident on each node (i.e.
Externí odkaz:
http://arxiv.org/abs/2311.11869
The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph $G$. Our goal is to find a subgraph $S$ of $G$ with the minimum number of edg
Externí odkaz:
http://arxiv.org/abs/2305.02240
Autor:
Abbasi, Fateme, Adamczyk, Marek, Bosch-Calvo, Miguel, Byrka, Jarosław, Grandoni, Fabrizio, Sornat, Krzysztof, Tinguely, Antoine
In the Submodular Facility Location problem (SFL) we are given a collection of $n$ clients and $m$ facilities in a metric space. A feasible solution consists of an assignment of each client to some facility. For each client, one has to pay the distan
Externí odkaz:
http://arxiv.org/abs/2211.05474
The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edges. One of the most basic problems in this area is the $2$-Edge-Connec
Externí odkaz:
http://arxiv.org/abs/2209.10265
In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum
Externí odkaz:
http://arxiv.org/abs/2209.05520
The Uncapacitated Facility Location (UFL) problem is one of the most fundamental clustering problems: Given a set of clients $C$ and a set of facilities $F$ in a metric space $(C \cup F, dist)$ with facility costs $open : F \to \mathbb{R}^+$, the goa
Externí odkaz:
http://arxiv.org/abs/2207.05150