Friday, November 1, 2013 — 3:30 PM to 4:30 PM EDT

Finding small stabilizers for unstable graphs

Speaker: Andrew Childs
Affiliation: University of Waterloo
Room: Mathematics and Computer Building (MC) 5158

Abstract:

A vertex v of a graph G is called inessential if there exists a maximum matching in G that exposes v. G is said to be stable if the set of its inessential vertices forms a stable set.

Stable graphs play a key role in network bargaining games where we are given a set of players represented as vertices of a graph G, and a set of possible deals between players represented by the edges of G. Kleinberg and Tardos [STOC ’08] defined the notion of a balanced outcome for a network bargaining game, and proved that a balanced outcome exists if and only if the correspondent graph G is stable.

This connection motivates the optimization problem of finding a minimum cardinality stabilizer of a given unstable graph G, that is a subset of edges F such that G\F is stable. In this talk we prove some structural results about this problem and develop efficient approximation algorithms for sparse graphs.

Joint work with A.Bock, K.Chandrasekaran, J.Koenemann, B.Peis

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (140)
    1. October (11)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)