CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Optimization, Geometry and Graphs
Org: Bruce Shepherd (UBC)

Revisiting the Core of Papadimitriou's Multi-Flow Game  [PDF]

Papadimitriou introduced a co-operative game which models interactions between autonomous systems in the Internet. While the game is known to have a non-empty core, in the non-transferable utility version the only algorithmic work is due to Yamada and Karasawa who study the case of a path. Their analysis is based on a left-to-right or right-to-left scan which produces two core vectors. We give a generalized algorithm that produces a larger set of core elements, which allows us to explore social trade-offs between different core strategies. Half of our analysis is based on a duality argument which extends to general networks.

Minimizing Interference Potential Among Moving Entities  [PDF]

Imagine a collection of entities moving with bounded speed in Euclidean space. Uncertainty in entity locations due to unmonitored and unpredictable motion gives rise to a space of possible entity configurations at each time. We define measures of the interference potential of such spaces to describe the interference that might actually occur. We study how limited monitoring rate impacts interference potential, and describe and analyse an adaptive monitoring scheme for minimizing interference potential over time that is competitive (to within a constant factor) with any other scheme (in particular, a clairvoyant scheme) over modest sized time intervals.

Finding Triangle-free 2-factors, Revisited  [PDF]

A 2-factor in a graph is a spanning subgraph whose connected components are cycles. Finding 2-factors in graphs is a well-studied problem. Many results are known including a polynomial-time algorithm and a related max-min theorem. This problem is a relaxation of the NP-hard problem of finding a Hamilton cycle. A stronger relaxation is the problem of finding a 2-factor containing no cycle of length 3. A polynomial-time algorithm and related max-min theorem for this problem were presented in the speaker’s Ph.D. thesis. Here we present a simpler polynomial-time algorithm for this problem and a newly formulated max-min theorem.

Scalable Misinformation Prevention in Social Networks  [PDF]

We consider misinformation propagating through a social network and study the problem of its prevention using a limiting campaign. The goal is to identify a set of $k$ users that need to be convinced to adopt the limiting campaign so as to minimize the number of people adopting the misinformation. We present RPS, an algorithm that provides a scalable solution to this problem. We experimentally evaluate RPS and show that it outperforms the state-of-the-art solution in terms of running time. Our work demonstrates that misinformation prevention can be made practical while still offering strong theoretical guarantees.

On the Circuit Diameter Conjecture  [PDF]

A key concept in optimization is the diameter of a polyhedron. From the point of view of optimization, we would like to relate it to the number of facets $f$ and dimension $d$ of the polyhedron. Following Klee and Walkup (1967), we consider analogous questions for a variant of the combinatorial diameter called the circuit diameter. Here paths are built from the circuit directions of the polyhedron, and can travel through the interior. We show that many of the Klee-Walkup results and techniques translate to the circuit setting.

Joint work with Steffen Borgwardt and Timothy Yusun.