Affiner les résultats

A new constructive heuristic driven by machine learning for the traveling salesman problem

Mele, Umberto Junior ; Gambardella, Luca Maria ; Montemanni, Roberto

In: Algorithms, 2021, vol. 14, no. 9, p. 25

Recent systems applying Machine Learning (ML) to solve the Traveling Salesman Problem (TSP) exhibit issues when they try to scale up to real case scenarios with several hundred vertices. The use of Candidate Lists (CLs) has been brought up to cope with the issues. A CL is defined as a subset of all the edges linked to a given vertex such that it contains mainly edges that are believed to be...

Graph neural networks : operators and architectures

Grattarola, Daniele ; Alippi, Cesare (Dir.) ; Livi, Lorenzo (Codir.)

Thèse de doctorat : Università della Svizzera italiana, 2021 ; 2021INFO014.

This thesis explores the field of graph neural networks, a class of deep learning models designed to learn representations of graphs. We organise the work into two parts. In the first part, we focus on the essential building blocks of graph neural networks. We present three novel operators for learning graph representations: one graph convolutional layer and two methods for pooling. We put...

Blocking Total Dominating Sets Via Edge Contractions

Galby, Esther ; Mann, Felix ; Ries, Bernard

In: Theoretical Computer Science, 2021, vol. 877, p. 18-35

In this paper, we study the problem of deciding whether the total domination number of a given graph Gcan be reduced using exactly one edge contraction (called1-Edge Contraction(γt)). We focus on several graph classes and determine the computational complexity of this problem. By putting together these results, we manage to obtain a complete complexity dichotomy for H-free graphs.

Communication and Coordination in a Two-Stage Game

Bjedov, Tjasa ; Madiès, Thierry ; Villeval, Marie Claire

In: Economic Inquiry, 2016, vol. 54, no. 3, p. 1519-1540

We study the impact of communication on behavior in a two-stage coordination game with asymmetric payoffs. We test experimentally whether individuals can avoid a head-to-head confrontation by means of coordinated strategies. In particular we analyze whether and how quickly a conflict-avoidance take turn strategy can emerge. First, our results show that players learn to solve the conflict by...

Balanced Partitions of Trees and Applications

Feldmann, Andreas ; Foschini, Luca

In: Algorithmica, 2015, vol. 71, no. 2, p. 354-376

The Banzhaf value in the presence of externalities

Álvarez-Mozos, M. ; Tejada, O.

In: Social Choice and Welfare, 2015, vol. 44, no. 4, p. 781-805

Equity dynamics in bargaining without information exchange

Nax, Heinrich

In: Journal of Evolutionary Economics, 2015, vol. 25, no. 5, p. 1011-1026

Mixed equilibria in Tullock contests

Ewerhart, Christian

In: Economic Theory, 2015, vol. 60, no. 1, p. 59-71

Eliciting Beliefs in Continuous-Choice Games: a Double Auction Experiment

Neri, Claudia

In: Experimental Economics, 2015, vol. 18, no. 4, p. 569-608

Pure Nash Equilibria in Graphical Games and Treewidth

Thomas, Antonis ; van Leeuwen, Jan

In: Algorithmica, 2015, vol. 71, no. 3, p. 581-604