# Navigation Area

# 2017

# Main content

## Seminar on Algorithms, Data Structures, and Applications, SOS

**Talks in this semester are usually given on Mondays 15:30 h, CAB H 52 or 53**

If you wish to receive email announcements of upcoming events, please subscribe to our SOS mailing list.

**Talks given 2017**

- 01.06.17, 11:00, CAB H 52, Kieran Nirkko: Mastermind Variants on Permutations.

Abstract: Mastermind is an asymmetric two player game where the Codemaker creates a secret code and the Codebreaker tries to guess the code by asking queries and receiving some feedback. We consider a variant of this game were both the secret and the queries are permutations of size n and the feedback is the number of correct positions. We are interested in the minimum number of queries that guarantee that the secret can be determined.

For the online (adaptive) version of this game we shown how the Codemaker can enforce the known Omega(n) bound in O(n^2.5) time. For the offline (non-adaptive) version we show that Theta(n log n) is optimal if the secret is fixed and provide an explicit O(n^2) strategy that determins the secret even when the Codemaker behaves like an adversary. We also provide the optimal bounds for n <= 5.

- 08.05.17, 15:30, CAB H 53, Lukas Gianinazzi: Cache Oblivious Minimum Cut.

Abstract: We show how to compute the minimum cut of a graph cache-efficiently. Let B be the width of a cache line and M be the size of the cache. On a graph with V vertices and E edges, we give a cache oblivious algorithm that incurs O(ceil{E/B log^4 E) log_{M/B} E}) cache misses and a simpler one that incurs O(ceil{V^2/B} log^3 V) cache misses.

- 20.03.17, 15:30, CAB H 53, Paolo Penna: Independent lazy better-response dynamics on network games.

Abstract: Game dynamics are typically simple algorithms (run by the players themselves) for computing Nash equilibria (in certain classes of games). Roughly speaking, there are two (somewhat orthogonal) features that one would like to have: the dynamics should be "simple/natural" and should converge "quickly" to the equilibrium.

The talks will then focus on a very simple type of dynamics (called independent best-response dynamics) on network games where the nodes (players) decide to revise their strategies independently with some probability. Unlike "classical" best-response dynamics, here there is no centralized schedule of the players moves and in principle simultaneous updates (best or better response) are possible.

We are interested in the convergence time to the equilibrium as a function of this probability, the degree of the network, and the potential of the underlying games.

These results are a joint work with Laurent Viennot: https://arxiv.org/pdf/1609.08953v1.pdf

- 13.03.17, 15:30, CAB H 53, Cong Chen: Online Machine Scheduling with Jobs of k Favorite Machine(s).

Abstract: This talk introduces a simple and natural variant of online machine scheduling. Two special cases of our model correspond to the classical identical machines and to the case of two related machines.

We give tight bounds on the competitive ratio of the Greedy algorithm and characterize the optimal competitive ratio for this problem in two machines.

And then we will give another variant which allows for a comparison with the case of unrelated machines.

- 07.03.16, 15:15, CAB H 53, Andreas Bärtschi: Energy-efficient Delivery by Heterogeneous Mobile Agents. Abstract: We consider the problem of delivering m messages between specified source-target pairs in an undirected graph, by k mobile agents initially located at distinct nodes of the graph. Each edge has a designated length and each agent consumes energy proportional to the distance it travels in the graph. We are interested in optimizing the total energy consumption for the team of agents. Unlike previous related work, we consider heterogeneous agents with different rates of energy consumptionv(weights). To solve the delivery problem, agents face three major challenges: Collaboration (how to work together on each message), Planning (which route to take) and Coordination (how to assign agents to messages).

We first show that the delivery problem can be 2-approximated without collaborating. This is best possible, i.e. one can show that the benefit

of collaboration is 2 in general. Planning turns out to be NP-hard to approximate even for a single agent, but can be 2-approximated in polynomial time if agents have unit capacities and do not collaborate. Coordination again is NP-hard even for agents with unit capacity, but can be efficiently solved exactly if they additionally have uniform weights. Finally, we give a polynomial-time (4 maxweight/minweight) approximation for message delivery with unit capacities.