9:30  10:30 
Plenary Session
Taking into account a society’s opinions on a multiplicity of issues in a way that avoids proclaiming dictators.
Lefteris Kirousis, National and Kapodistrian University of Athens
Abstract: Assume that the members of a society of individuals are given the chance to express an opinion on a multiplicity of issues.
The opinion of an individual on an issue can take one of several values, however only certain combinations of an individual’s opinions on the issues are considered to be rational.
Given the set of rational combinations, can we efficiently decide whether any collection of such combinations by the individuals can be aggregated into a single rational combination in a way that avoids
proclaiming one particular individual as a dictator and always following their opinion?
Joint work with Phokion Kolaitis and John Livieratos

11:00  12:00 
Session 1
Network Pricing: How to Induce Optimal Flows Under Strategic Link Operators
Thanasis Lianeas, National Technical University of Athens
Abstract: Network pricing games provide a framework for modeling realworld settings with two types of strategic agents: owners (operators) of the network and users of the network. Owners of the network post a price for usage of the link they own so as to attract users and maximize profit; users of the network select routes based on price and level of use by other users. We point out that an equilibrium in these games may not exist, may not be unique and may induce an arbitrarily inefficient network performance.
Our main result is to observe that a simple regulation on the network owners market solves all three issues above. Specifically, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge, then: the game among the link operators has a unique and strong Nash equilibrium and the users' game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls. As a secondary objective, we want to compute great tolls that minimize total users' payments and we provide a linear program that does this. We obtain multiplicative approximation results compared to the optimal total users' payments for arbitrary networks with polynomial latencies of bounded degree, while in the singlecommodity case we obtain a bound that only depends on the topology of the network. Lastly, we show how the same mechanism of setting appropriate caps on the allowable prices extends to the model of elastic demands.
Algorithms for Stable and PerturbationResilient Problems
Haris Angelidakis, Toyota Technological Institute at Chicago
Abstract: We study a beyond worstcase analysis framework known as stability and perturbation resilience, introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A combinatorial optimization problem is $\gamma$stable or $\gamma$perturbationresilient if the optimal solution does not change when we perturb all parameters of the problem by a factor of at most $\gamma$. In this talk, we start with a brief survey of known results in the area, and then present exact polynomialtime algorithms for stable instances of Edge/Node Multiway Cut and Independent Set. We then proceed to explore the power of convex relaxations for solving stable instances of combinatorial optimization problems. We conclude with several hardness results for stable instances of covering problems.
Based on joint works with Konstantin Makarychev and Yury Makarychev, and Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis and Chen Dan.

12:15  13:15 
Session 2
Maximum Rooted Connected Expansion
Ioannis Lamprou, University of Liverpool
Abstract: Prefetching constitutes a valuable tool toward efficient Web surfing. As a
result, estimating the amount of resources that need to be preloaded during a
surfer's browsing becomes an important task. In this regard, prefetching can be
modeled as a twoplayer combinatorial game [Fomin et al., Theoretical Computer
Science 2014], where a surfer and a marker alternately play on a given graph
(representing the Web graph). During its turn, the marker chooses a set of $k$
nodes to mark (prefetch), whereas the surfer, represented as a token resting on
graph nodes, moves to a neighboring node (Web resource). The surfer's objective
is to reach an unmarked node before all nodes become marked and the marker
wins. Intuitively, since the surfer is stepbystep traversing a subset of
nodes in the Web graph, a satisfactory prefetching procedure would load in
cache all resources lying in the neighborhood of this growing subset.
Motivated by the above, we consider the following problem to which we refer
to as the Maximum Rooted Connected Expansion (MRCE) problem. Given a graph $G$ and a root node $v_0$, we wish to find a subset of vertices $S$ such that $S$
is connected, $S$ contains $v_0$ and the ratio $N[S]/S$ is maximized, where
$N[S]$ denotes the closed neighborhood of $S$, that is, $N[S]$ contains all
nodes in $S$ and all nodes with at least one neighbor in $S$.
We prove that the problem is NPhard even when the input graph $G$ is
restricted to be a split graph. On the positive side, we demonstrate a
polynomial time approximation scheme for split graphs. Furthermore, we present
a $\frac{1}{6}(1\frac{1}{e})$approximation algorithm for general graphs based
on techniques for the Budgeted Connected Domination problem [Khuller et al.,
SODA 2014]. Finally, we provide a polynomialtime algorithm for the special
case of interval graphs.
Joint work with R. Martin, S. Schewe, I. Sigalas, V. Zissimopoulos
Improved Approximation for Tree Augmentation: Saving by Rewiring
Christos Kalaitzis, ETH Zürich
Abstract:The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called links. The task is to find a set of links, of minimum size, whose addition to the tree leads to a 2edgeconnected graph. A long line of results on TAP culminated in the previously best known approximation guarantee of 1.5. We show that an approximation factor below 1.5 can be achieved, by presenting a 1.458approximation that is based on several new techniques.

14:45  15:45 
Session 3
Truthful mechanisms for ownership transfer with expert advice
Ioannis Caragiannis, University of Patras
Abstract:When a company undergoes a merger or transfer of its ownership, the existing governing body has an opinion on which buyer should take over as the new owner. Similar situations occur while assigning the host of big sports tournaments, e.g., the World Cup or the Olympics. In all these settings, the values of the external bidders are as important as the internal experts' opinions. Motivated by such questions, we consider a social welfare maximizing approach to design and analyze truthful mechanisms in these settings. We consider the problem with one expert and two bidders and provide tight approximation guarantees of the optimal social welfare. Since this problem is a combination of mechanism design with and without monetary transfers (payments can be imposed to the bidders but not to the expert), classical solutions like VCG cannot be applied, making this a novel mechanism design problem. We distinguish between mechanisms that use ordinal and cardinal information, as
well as between mechanisms that base their decisions on one of the two sides (either the bidders or the expert) or both. Our analysis shows that the cardinal setting is quite rich and admits several nontrivial randomized truthful mechanisms, and also allows for closertooptimalwelfare guarantees.

16:00  17:00 
Session 4
A combinatorial approach to the recovery of Gaussian Graphical Models
Vasiliki Velona, Universitat Pompeu Fabra, Universitat Politècnica de Catalunya
Abstract: Suppose that $X=(X_1,...,X_n)$ follows a multivariate normal distribution with precision matrix Q and G(V,E) is the underlying graph of Q, i.e., an edge ij belongs in E if and only if $q_{ij}$ is not zero. We give randomised algorithms that recover efficiently the graph G, under some graph theoretic assumptions. Moreover, we give lower bounds on the number of pairwise correlations needed to recover G. We pursue to extend our results to more general classes of graphs.
This is joint (and ongoing) work with Gábor Lugosi, Jakub Truszkowski, and Piotr Zwiernik.
Local Differential Privacy
Angelina Vidali, National and Kapodistrian University of Athens
Abstract:Local Differential Privacy has recently attracted much attention as a privacy metric in the local model, in which each user adds noise to his own personal data by himself and the data aggregator estimates the statistics of the personal data such as a distribution underlying the data. Local Differential Privacy provides a privacy guarantee against adversaries with arbitrary background knowledge, and does not suffer from a possibility of data leakage. It is very useful in practice because users don't need to trust the data aggregator to be willing to give their data.
