5,569 research outputs found
Hedonic Games with Fixed-Size Coalitions
No full textIn hedonic games, a set of n agents, having preferences over all possible coalition structures, needs to agree on a stable outcome. In this work, we initiate the study of hedonic games with fixed-size coalitions, where the set of possible coalition structures is restricted as follows: there are k coalitions, each coalition has a fixed size, and the sum of the sizes of all coalitions equals n. We focus on the basic model of additively separable hedonic games with symmetric preferences, where an agent's preference is captured by a utility function which sums up a contribution due to any other agent in the same coalition. In this setting, an outcome is stable if no pair of agents can exchange coalitions and improve their utilities. Conditioned on the definition of improvement, three stability notions arise: swap stability under transferable utilities, which requires to improve the sum of the utilities of both agents, swap stability, which requires to improve the utility of one agent without decreasing the utility of the other one, and strict swap stability, requiring to improve the utilities of both agents simultaneously. We analyse the fundamental questions of existence, complexity and efficiency of stable outcomes, and that of complexity of a social optimum
Blackout-Tolerant Temporal Spanners
No full textIn this paper we introduce the notions of blackout-tolerant temporal -spanner of a temporal graph G which is a subgraph of G that preserves the distances between pairs of vertices of interest in G up to a multiplicative factor of, even when the graph edges at a single time-instant become unavailable. In particular, we consider the single-source, single-pair, and all-pairs cases and, for each case we look at three quality requirements: exact distances (i.e.,), almost-exact distances (i.e., for an arbitrarily small constant), and connectivity (i.e., unbounded). For each combination we provide tight bounds, up to polylogarithmic factors, on the size, which is measured as the number of edges, of the corresponding blackout-tolerant-spanner for both general temporal graphs and for temporal cliques. Our result show that such spanners are either very sparse (i.e., they have edges) or they must have size in the worst case, where n is the number of vertices of G. To complete the picture, we also investigate the case of multiple blackouts
Sparse Temporal Spanners with Low Stretch
No full textA temporal graph is an undirected graph G = (V,E) along with a function λ : E → N+ that assigns a time-label to each edge in E. A path in G such that the traversed time-labels are non-decreasing is called a temporal path. Accordingly, the distance from u to v is the minimum length (i.e., the number of edges) of a temporal path from u to v. A temporal α-spanner of G is a (temporal) subgraph H that preserves the distances between any pair of vertices in V , up to a multiplicative stretch factor of α. The size of H is measured as the number of its edges. In this work, we study the size-stretch trade-offs of temporal spanners. In particular we show that temporal cliques always admit a temporal (2k -1)-spanner with eO(kn1+1k ) edges, where k > 1 is an integer parameter of choice. Choosing k = log n⌉, we obtain a temporal O(log n)-spanner with eO(n) edges that has almost the same size (up to logarithmic factors) as the temporal spanner given in [Casteigts et al., JCSS 2021] which only preserves temporal connectivity. We then turn our attention to general temporal graphs. Since Ω(n2) edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that eO(n/ log(1 + ε)) edges suffice to obtain a stretch of (1 + ε), for any small ε > 0. This result is essentially tight in the following sense: There are temporal graphs G for which any temporal subgraph preserving exact distances from a single-source must use Ω(n2) edges. Interestingly enough, our analysis can be extended to the case of additive stretch for which we prove an upper bound of eO(n2/β) on the size of any temporal β-additive spanner, which we show to be tight up to polylogarithmic factors. Finally, we investigate how the lifetime of G, i.e., the number of its distinct time-labels, affects the trade-off between the size and the stretch of a temporal spanner
Tessiture dello spazio. Tre progetti di Giancarlo De Carlo del 1961
No full textQuesto libro si occupa di tre architetture di Giancarlo De Carlo e
in particolare di un certo modo di pensare e manipolare lo spazio.
I tre progetti hanno tutti a che fare con il Mediterraneo, passione
costante dell’autore di Viaggi in Grecia, cresciuto in città di mare
come Genova, Trieste, Livorno e Tunisi. Si tratta rispettivamente
della colonia a Riccione, costruita e inaugurata nel 1963, la casa di
vacanze a Bordighera, costruita e inaugurata nel 1966, e la colonia
marina a Classe, nei pressi di Ravenna, non realizzata.
Considerati nel loro insieme, questi tre progetti definiscono, nel
curriculum professionale di De Carlo, un piccolo ma riconoscibile
corpus di lavori, apparentati dai programmi, simili e confrontabili,
dalle dimensioni, anch’esse simili, e dall’anno di redazione dei progetti:
tutti e tre infatti sono del 1961 vale a dire appena successivi
alla fine dei ciam e all’inizio dell’avventura del Team 10, di cui De
Carlo è stato un protagonista indiscusso, e appena prima della
grande avventura progettuale urbinate. In ogni caso questi progetti
vanno inquadrati in un contesto di confronto europeo, specie
con il lavoro coevo di Aldo van Eyck o Alison e Peter Smithson.
La finalità dell’autore non è quella di revisionare la collocazione
storico-critica del maestro genovese, bensì di restituire ai ragionamenti
contemporanei sull’architettura la ricchezza di riflessioni intorno
alla nozione di spazio tanto cruciale quanto sostenuta dalla
metafora tessile, alla base anche dell’idea di «rammendo» urbano
oggi tanto in voga. Proprio in questi progetti decarliani, precisa
ancora l’autore, «Lo spazio, pertanto, è articolato in vere e proprie
tessiture, definite da attività e usi, da dimensioni e materie, da luce
e sequenze ecc. Tali tessiture non sono stabili, ma soggette a un
constante lavorio di modificazione, che costituisce l’evoluzione dei
luoghi e dei gruppi sociali nel tempo»
L'architettura di sopravvivenza. Una filosofia della povertà
No full textUn ragionamento condotto a partire dal libro di Yona Friedman, pubblicato nel lontano 1978 ma sempre attuale, dal titolo: L'architettura di sopravvivenza. Una filosofia della povertà
You can't put the clock back. Townscape e cultura del paesaggio su Architectural Review negli anni '50
No full textIl testo si occupa di Townscape e di cultura del paesaggio, per come sono elaborati dalla cultura architettonica inglese negli anni Cinquanta sulle pagine del periodico "Architectural Review"
Il Municipio di Fiumicino, Roma
No full textL'articolo propone una lettura dell'edificio costruito da Alessandro Anselmi a Fiumicin
- …
