Lista referatów

• 2018-11-22, godz. 10:15, 4050

  Oskar Skibski (Instytut Informatyki, UW)

  Attachment Centrality: Properties and Computation

  Centrality indices aim to quantify the importance of nodes or edges in a network. Much interest has been recently raised by the body of work in which a node’s connectivity is understood less as its contribution to the quality or speed of communication in the network and more as its role in ena...

• 2018-11-08, godz. 10:15, 4050

  Tomasz Wąs (Instytut Informatyki UW)

  Random Walk Decay Centrality

  We propose a new centrality measure, called the Random Walk Decay centrality. While most centralities in the literature are based on the notion of shortest paths, this new centrality measure stems from the random walk on the network. We provide an axiomatic characterization and show that the new cen...

• 2018-10-26, godz. 12:15, 4050

  Dominik Peters (Department of Computer Science, University of Oxford)

  Allocation of Indivisible Items with Connected Bundles

  Suppose a collection of indivisible goods are arranged in a line, and we wish to allocate these items to agents so that each agent receives a connected bundle (an interval). This makes sense when the items have a spatial or temporal structure, for example when allocating time slots, and agents are i...

• 2018-10-18, godz. 10:15, 4050

  Marcin Dziubiński (Instytut Informatyki, UW)

  How to hide in a network

  We propose and study a strategic model of hiding in a network, where the network designer chooses the links and his position in the network facing the seeker who inspects and disrupts the network. We characterize optimal networks for the hider, as well as equilibrium hiding and seeking strategies on...

• 2018-05-10, godz. 10:15, 4050

  Tomasz Wąs (Instytut Informatyki, UW)

  Axiomatization of the PageRank centrality

  We propose an axiomatization of PageRank. Specifically, we introduce five simple axioms – Foreseeability, Outgoing Homogeneity, Monotonicity, Merging, and Dummy Node – and show that PageRank is the only centrality measure that satisfies all of them. Our axioms give new conceptual and ...

• 2018-04-12, godz. 10:15, 4050

  Piotr Skowron (Instytut Informatyki UW)

  Approximating Optimal Social Choice under Metric Preferences

  We consider voting under metric preferences: both voters and alternatives are associated with points in a metric space, and each voter prefers alternatives that are closer to her to ones that are further away. In this setting, it is often desirable to select an alternative that minimizes the sum of ...

• 2018-03-29, godz. 10:15, 4050

  Krzysztof Rządca (Instytut Informatyki, UW)

  Collective Schedules: Scheduling Meets Computational Social Choice

  When scheduling public works or events in a shared facility one needs to accommodate preferences of a population. We formalize this problem by introducing the notion of a collective schedule. We show how to extend fundamental tools from social choice theory---positional scoring rules, the Kemeny ru...

• 2018-03-15, godz. 10:15, 4790

  Jadwiga Sosnowska (Instytut Informatyki UW)

  Path Evaluation and Centralities in Weighted Graphs – An Axiomatic Approach

  We study the problem of extending the classic centrality measures to weighted graphs. Unfortunately, in the existing extensions, paths in the graph are evaluated solely based on their weights, which is a restrictive and undesirable assumption for a variety of settings. Given this, we define a notion...

• 2018-01-25, godz. 10:15, 4790

  Rahul CS (Instytut Informatyki, UW)

  Group Activity Selection parameterized by the Number of Agent Types

  We study the parameterized complexity of GASP (Group Activity Selection Problem) and its variant gGASP w.r.t. the number of different agent types as a parameter. We show that GASP can be solved in polynomial time if the number of agent types is a constant and complement this result with a strong par...

• 2018-01-11, godz. 10:15, 4790

  Oskar Skibski (Instytut Informatyki, UW)

  A Pseudo-Polynomial Algorithm for Computing Power Indices in Graph-Restricted Weighted Voting Games

  Weighted voting games allow for studying the distribution of power between agents in situations of collective decision making. While the conventional version of these games assumes that any agent is always ready to cooperate with all others, recently, more involved models have been proposed, where c...

Strony