Concept
Graphe de disques
Publications associées (16)
Graph Exploration for Effective Multiagent Q-Learning
This article proposes an exploration technique for multiagent reinforcement learning (MARL) with graph-based communication among agents. We assume that the individual rewards received by the agents are independent of the actions by the other agents, while ...
Ieee-Inst Electrical Electronics Engineers Inc2024Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
Martin Jaggi, Sebastian Urban Stich, Anastasiia Koloskova
We consider decentralized stochastic optimization with the objective function (e.g. data samples for machine learning task) being distributed over n machines that can only communicate to their neighbors on a fixed communication graph. To reduce the communi ...
2019An Optimal Space Lower Bound for Approximating MAX-CUT
We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output hal ...
ASSOC COMPUTING MACHINERY2019Filtering Random Graph Processes Over Random Time-Varying Graphs
Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deterministic setting, ignoring the impact of stochasticity i ...
Institute of Electrical and Electronics Engineers2017Exponential extinction time of the contact process on finite graphs
Thomas Mountford, Daniel Rodrigues Valesin, Jean-Christophe Mourrat
We study the extinction time tau of the contact process started with full occupancy on finite trees of bounded degree. We show that, if the infection rate is larger than the critical rate for the contact process on Z, then, uniformly over all trees of degr ...
Elsevier Science Bv2016Unsplittable Coverings in the Plane
A system of sets forms an m-fold covering of a set X if every point of X belongs to at least m of its members. A 1-fold covering is called a covering. The problem of splitting multiple coverings into several coverings was motivated by classical density est ...
Springer-Verlag Berlin2016Unsplittable coverings in the plane
A system of sets forms an m-fold covering of a set X if every point of X belongs to at least m of its members. A 1-fold covering is called a covering. The problem of splitting multiple coverings into several coverings was motivated by classical density est ...
Academic Press Inc Elsevier Science2016Coloring Intersection Graphs of Arc-Connected Sets in the Plane
Bartosz Maria Walczak, Michal Lason
A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line L if the intersection of any member with L is a nonempty segment. It is proved that the intersection graphs of simple families of com ...
Springer2014Coloring Relatives of Interval Overlap Graphs via On-line Games
The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs defined by geometric representations and competitivity analysis of on-line algorithms. This connection became apparent after the recent construction ...
Springer-Verlag Berlin2014Efficient graph planarization in sensor networks and local routing algorithm
In this paper, we propose an efficient planarization algorithm and a routing algorithm dedicated to Unit Disk Graphs whose nodes are localized using the Virtual Raw Anchor Coordinate system (VRAC). Our first algorithm computes a planar 2-spanner under ligh ...
Ieee2012