9:30  10:30 
Plenary Session
Symmetry Breaking in the Plane: Rendezvous by Robots with Unknown Attributes
Evangelos Kranakis, Carleton
Abstract:
We study a fundamental question related to the feasibility of deterministic symmetry breaking in the infinite Euclidean plane for two robots that have minimal or no knowledge of the respective capabilities and ``measuring instruments'' of themselves and each other. Assume that two anonymous mobile robots are placed at different locations at unknown distance $d$ from each other on the infinite Euclidean plane. Each robot knows neither the location of itself nor of the other robot. The robots cannot communicate wirelessly, but have a certain nonzero visibility radius $r$ (with range $r$ unknown to the robots). By rendezvous we mean that they are brought at distance at most $r$ of each other by executing symmetric (identical) mobility algorithms. The robots are moving with unknown, constant but not necessarily identical speeds, their clocks and pedometers may be asymmetric, and their chirality inconsistent.
We demonstrate that rendezvous for two robots is feasible under the studied model iff the robots have either: different speeds; or different clocks; or different orientations but equal chiralities. When the rendezvous is feasible, we provide a universal algorithm which always solves rendezvous despite the fact that the robots have no knowledge of which among their respective parameters may be different.
Paper presented in PODC 2019: Joint work with Jurek Czyzowicz, Leszek Gasieniec, and Ryan Killick

11:00  13:00 
Session 3
Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, KCL
Abstract:
We present new tradeoffs between space and querytime for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, subpolynomial or arbitrarily small polynomial factors from the na\"{\i}ve linear space, constant querytime lower bound. These tradeoffs include: (i) an oracle with space $\mathcal{O}(n^{1+\epsilon})$ and querytime $\tilde{\mathcal{O}}(1)$ for any constant $\epsilon>0$, (ii) an oracle with space $\tilde{\mathcal{O}}(n)$ and querytime $\mathcal{O}(n^{\epsilon})$ for any constant $\epsilon>0$, and (iii) an oracle with space $n^{1+o(1)}$ and querytime $n^{o(1)}$.
Approximation algorithms for packet routing
Timos Aslanidis, NTUA
Abstract:
The problem to be presented is referred to and encountered in various forms in international
bibliography and has many applications as far as Optical Networks,
TDMA (Time Division Multiple Access) and parallel message or data transmission are concerned.
For the purposes of this presentation the graph theoretic model of the problem will be used.
Researchers are referring to the problem at hand as PREEMPTIVE BIPARTITE SCHEDULING (PBS).
In its various forms it has been studied extensively by many researchers and scholars.
It is described as follows:
Given a set of transmission stations (a set of vertices V, V=n), a set of receivers U
(a set of vertices U, U=m) and a set of messages to be transmitted from V to U
(a set of edges E), we are required to produce an efficient schedule such that
the total time duration from beginning of the first transmission to the conclusion of the last
will be minimized. Each of the messages to be transmitted has some specific duration
(edges weight: w). To achieve our goal we are allowed to interrupt (preempt) message packages.
Unfortunately, preemption comes with a cost (delay=d) in order to reconfigure
the system and/or prepare for the next transmission. Each time we decide to preempt,
a reconfiguration delay add to the total transmission time.
Therefor in order to produce an optimal schedule one has to take into account two different
parameters simultaneously.
The approximation algorithms to be presented aim in pinpointing different methodolies in order to
efficiently tackle NPHard problems.
When Does Diversity of User Preferences Improve Outcomes in Selfish Routing?
Thanasis Lianeas, NTUA
Abstract:
We seek to understand when heterogeneity in user preferences yields improved outcomes in terms of overall cost. That this might be hoped for is based on the common belief that diversity is advantageous in many settings. We investigate this in the context of routing. Our main result is a sharp characterization of the network settings in which diversity always helps, versus those in which it is sometimes harmful. Specifically, we consider routing games, where diversity arises in the way that users tradeoff two criteria (such as time and money, or, in the case of stochastic delays, expectation and variance of delay). Our main contributions—a
conceptual and a technical one— are the following:
1) A participantoriented measure of cost in the presence of user diversity, together with the identification of the natural benchmark: the same cost measure for an appropriately defined average of the diversity.
2) A full characterization of those network topologies for which diversity always helps, for all latency functions and demands. For singlecommodity routings, these are seriesparallel graphs, while for multicommodity routings, they are the newlydefined “blockmatching” networks. The latter comprise a suitable interweaving of multiple seriesparallel graphs each connecting a distinct sourcesink pair.
While the result for the singlecommodity case may seem intuitive in light of the wellknown Braess paradox, the two problems are different: there are instances where diversity helps although the Braess paradox occurs, and viceversa. But the main technical challenge is to establish the “only if” direction of the result for multicommodity networks. This follows by constructing an instance where diversity hurts, and showing how to embed it in any network which is not blockmatching, by carefully exploiting the way the simple sourcesink paths of the commodities intersect in the “nonblockmatching” portion of the network.
The Complexity of BlackBox Mechanism Design with Priors
Evangelia Gergatsouli, WisconsinMadison
Abstract:
We study blackbox reductions from mechanism design to algorithm design for welfare maximization in
settings of incomplete information. Given oracle access to an algorithm for an underlying optimization
problem, the goal is to simulate an incentive compatible mechanism. The mechanism will be evaluated on its
expected welfare, relative to the algorithm provided, and its complexity is measured by the time (and queries)
needed to simulate the mechanism on any input. While it is known that blackbox reductions are not possible
in many priorfree settings, settings with priors appear more promising: there are known reductions for
Bayesian incentive compatible (BIC) mechanism design for general classes of welfare maximization problems.
This dichotomy begs the question: which mechanism design problems admit blackbox reductions, and which
do not?
Our main result is that blackbox mechanism design is impossible under two of the simplest settings not
captured by known positive results. First, for the problem of allocating n goods to a single buyer whose
valuation is additive and independent across the goods, subject to a downwardclosed constraint on feasible
allocations, we show that there is no polytime (in n) BIC blackbox reduction for expected welfare maximization.
Second, for the setting of multiple singleparameter agents—where polytime BIC reductions are known—we
show that no polytime reductions exist when the incentive requirement is tightened to MaxInDistributional
Range. In each case, we show that achieving a subpolynomial approximation to the expected welfare requires
exponentially many queries, even when the set of feasible allocations is known to be downwardclosed.

15:00  16:30 
Session 4
Lower bounds for MaxCut in Hfree graphs
Alexandra Kolla, Colorado Boulder
Abstract:
For a graph G, let f(G) denotes the size of the maximum cut in G. The problem of estimating
f(G) as a function of the number of vertices and edges of G has a long history and was extensively
studied in the last fty years. In this paper we propose an approach, based on semidenite
programming (SDP), to prove lower bounds on f(G). We use this approach to nd large cuts
in graphs with few triangles and in Krfree graphs.
Joint work with Charles Carlson, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan
Improved Budgeted Connected Domination and Budgeted EdgeVertex Domination
Ioannis Sigalas, UoA
Abstract:
We consider the budgeted version of the classical connected dominating set problem (BCDS).
Given a graph G and an integer budget k, we seek to find a connected subset of at most k vertices which maximizes the number of dominated vertices in G.
We answer an open question in S. Khuller, M. Purohit, and K.K. Sarpatwar (Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems, SODA 2014) and thus we improve over the previous (11/e)/13 approximation.
Our algorithm provides a (11/e)/7 approximation guarantee by employing an improved method for enforcing connectivity and performing tree decompositions.
We also consider the edgevertex domination variant, where an edge dominates its endpoints and all vertices neighboring them.
In budgeted edgevertex domination (BEVD), we are given a graph G, and a budget k, and we seek to find a, not necessarily connected, subset of edges such that the number of dominated vertices in G is maximized.
We prove there exists a (11/e)approximation algorithm.
Also, for any ε > 0, we present a (11/e+ε)inapproximability result by a gappreserving reduction from the maximum coverage problem.
We notice that, in the connected case, BEVD becomes equivalent to BCDS.
Moreover, we examine the "dual" partial edgevertex domination(PEVD) problem, where a graph G and a quota n' are given.
The goal is to select a minimumsize set of edges to dominate at least n' vertices in G.
In this case, we present a H(n')approximation algorithm by a reduction to the partial cover problem.
Tight Bounds for Deterministic hShot Broadcast in AdHoc Directed Radio Networks
Aris Pagourtzis, NTUA
Abstract:
We consider the classical broadcast problem in adhoc (that is, unknown topology) directed radio networks with no collision detection, under the additional assumption that at most $h$ transmissions (shots) are available per node. We focus on adaptive deterministic protocols for small values of h. We provide asymptotically matching lower and upper bounds for the cases $h=2$ and $h=3$. While for $h=2$ our bound is quadratic, similar to the bound obtained for oblivious protocols, for $h=3$ we prove a subquadratic bound of $\Theta(n^2 \log \log n / \log n)$, where $n$ is the number of nodes in the network. The latter is the first result showing an adaptive algorithm which is asymptotically faster than oblivious $h$shot broadcast protocols, for which a tight quadratic bound is known for every constant $h$. Our upper bound for $h=3$ is constructive, making use of constructions of graphs with large girth. We also show an improved upper bound of $O(n^{(1+\alpha/\sqrt{h})})$ for $h \ge 4$, where $\alpha$ is an absolute constant independent of $h$. Our upper bound for $h \ge 4$ is nonconstructive.
(Joint work with Tomasz Radzik)
