Seminars2021
| ACiD Seminars 2020/21 | |
| Term 1 | |
| Tues 6 Oct 2020 13:00 online | |
| Tues 13 Oct 2020 13:00 online | |
| Tues 20 Oct 2020 13:00 online | Flavia Bonomo (Buenos Aires) On the thinness and proper thinness of a graph The thinness of a graph is a with parameter introduced by Mannino, Oriolo, Ricci, and Chandran in 2007 as a generalization of interval graphs, which are exactly the 1-thin graphs. When a representation of the graph as a k-thin graph is given, for a constant value k, some NP-complete problems as maximum weighted independent set and bounded coloring with fixed number of colors can be solved in polynomial time. Similarly, the graphs with bounded proper thinness generalize proper interval graphs. In this talk we will survey the main known results and open problems on thinness and proper thinness. We present the complexity of problems related to the computation of thinness and proper thinness, describe lower and upper bounds, the behavior of the thinness and proper thinness under some graph operations, and relate thinness and proper thinness to other graph invariants in the literature. We will describe also a wide family of problems that can be solved in polynomial time for graphs with bounded thinness, when the k-thin representation of the graph is given. For thinness and proper thinness two, we will present characterizations by means of intersection models and forbidden patterns. We will also relate graphs with thinness at most three to VPG graphs with bounded bend number. |
| Tues 27 Oct 2020 13:00 online | Agnes Cseh (Potsdam) Weakly and strongly popular rankings Van Zuylen et al. introduced the notion of a popular ranking in a voting context, where each voter submits a strictly ordered list of all candidates. A popular ranking pi of the candidates is better than any other ranking sigma in the following sense: if we compare pi to sigma, a majority of all voters will always weakly prefer pi. Whether a voter prefers one ranking to another is calculated based on the Kendall distance. A more traditional definition of popularity—as applied to popular matchings, a well-established topic in computational social choice—is stricter, because it requires a majority of voters who are not indifferent between pi and sigma to prefer pi. In this talk, I will present structural and algorithmic results in both settings, also improving upon the results of van Zuylen et al. I will also point out strong connections to the famous open problem of finding a Kemeny consensus with 3 voters. Joint work with Sonja Kraiczy and David Manlove. |
| Tues 3 Nov 2020 13:00 online | *** ACiD Meeting *** |
| Tues 10 Nov 2020 13:00 online | Erik Jan van Leeuwen (Utrecht) Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces This talk surveys some of the recent techniques to solve parameterized optimization problems on planar graphs, with a focus on the Steiner Tree problem. Many problems on planar graphs, such as deciding whether an n-vertex graph has a vertex cover of size at most k, are known to be decidable in 2^O(sqrt(k)) n^O(1) time, while such subexponential-time algorithms do not exist on general graphs, unless the Exponential Time Hypothesis fails. The standard techniques to obtain subexponential-time algorithms on planar graphs, however, are not applicable to the Steiner Tree problem. In the talk, I will describe the recent progress on this problem for various relevant parameters before focusing on the case that all terminals can be covered by the boundary of k faces. Erickson et al. [Math. Oper. Res., 1987] showed that this problem can be solved in n^O(k) time and n^O(k) space. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts. In recent joint work with Sandor Kisfaludi-Bak and Jesper Nederlof [SODA 2019/TALG 2020], we show a subexponential-time algorithm for this problem with running time 2^O(k) n^O(sqrt(k)) using only polynomial space. Furthermore, we show that the running time of the algorithm is almost tight: we prove that there is no f(k) n^o(sqrt(k)) time algorithm for any computable function f, unless the Exponential Time Hypothesis fails. |
| Tues 17 Nov 2020 13:00 online | Amitabh Trehan (Durham) Some Algorithmic Explorations In Message Passing Distributed Networks We do a brief and very high level exploration of the landscape of distributed computing. Distributed computing is the world of computing where independent computing devices do computation and solve problems by communicating with each other. It abstracts a vast universe of real world situations away from the world of centralised computing on a single computing device. At the simplest, these range from the tightly coupled interaction of the shared memory model (say, multiprocessors on a motherboard) to the message passing model (Communication Networks). However, there are an almost innumerable number of parameters to consider leading to a vast number of important models for the the abstractions and algorithm design. Overwhelmingly still the abstraction is to model the network as a graph with the vertices being nodes and communication links being the edges. We will briefly visit some of our recent works in different settings. In particular, we will look at two works at different scales of the spectrum. In our [STACS’20] paper, we look at Amnesiac Flooding: a very simple process/algorithm on even the simplest network – a node sends a message to all its neighbours and the only action they do is further forward copies to all except the ones they received from in that round. The questions are: Will this message circulate forever or flooding will terminate? What if there are multiple initiators? [AF-ARXIV’20] In [PODC’20], we are in a very different setting: An overlay/peer-to-peer network, where nodes are actually able to change edges when required. We know certain network/graph topologies such as expanders have very good properties enabling efficient communication. Here, we introduce a DC superhero (algorithm) DConstructor that takes any connected network and with only polylogarithmic (in number of nodes) communication among the nodes converts the network topology to a `good’ topology such as an expander. [STACS’20] Walter Hussak, Amitabh Trehan: On the Termination of Flooding. STACS 2020: 17:1-17:13 [AF-ARXIV’20] Walter Hussak, Amitabh Trehan: Terminating cases of flooding. CoRR abs/2009.05776 (2020) [PODC’20] Seth Gilbert, Gopal Pandurangan, Peter Robinson, Amitabh Trehan: DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead. PODC 2020: 438-447 |
| Tues 24 Nov 2020 13:00 online | John Fearnley (Liverpool) A faster algorithm for finding Tarski fixed points Dang et al. have given an algorithm that can find a Tarski fixed point in a k-dimensional lattice of width n using O(log^k n) queries. Multiple authors have conjectured that this algorithm is optimal, and indeed this has been proven for two-dimensional instances. We show that these conjectures are false in dimension three or higher by giving an O(log^2 n) query algorithm for the three-dimensional Tarski problem, which generalises to give an O(log^{k−1} n) query algorithm for the k-dimensional problem when k ≥ 3. Paper on arxiv: https://arxiv.org/abs/2010.02618 |
| Tues 1 Dec 2020 13:00 online | Riccardo Mogre (Durham) Dynamic Project Expediting: A Stochastic Shortest-Path Approach A decision maker is in charge of a project whose progress is random because of disruptions or productivity problems. In each time period, the manager reviews the progress and decides whether to expedite each activity. Her problem is to identify expediting policies that minimize her expected cost, given by the sum of the cost of expediting and a cost linear in the project completion time. We propose a infinite-horizon Markov decision process to identify optimal expediting policies for the execution of projects. We show that our problem belongs to a class of stochastic shortest-path problems which have some special ordering properties, which we call “forward-only stochastic shortest-path problems.” The enumeration of the feasible states for our problem is very difficult, primarily because of the precedence constraints in the network. For this reason, we devise algorithms to identify all the feasible states of the problem. The complexity of this problem renders impractical the use of existing algorithms employed to solve stochastic shortest-path problems. For this reason, we devise an exact, computationally-efficient algorithm to solve forward-only stochastic shortest-path problems. We complement our analytical results with a computational study that shows the computation times for various randomly generated networks. |
| Tues 8 Dec 2020 13:00 online | Antonio Porreca (Université Publique) Algebraic analysis of discrete dynamical systems Inspired by the category-theoretic operations of sum and product in the category of finite, discrete-dimes dynamical systems (which correspond to alternative and synchronous execution of the systems), we define a semiring structure to allow us to express certains decomposition problems in terms of factorisation and polynomial equations. We show that this semiring of dynamical systems is algebraically quite complex (the majority of dynamical systems is irreducible, but reducible ones sometimes admit multiple factorisations) and investigate the computability and complexity of solving polynomial equations. These turn out to be undecidable in general, and we prove that even the restricted case of linear equations is NP-hard. |
| Term 2 | |
| Tues 12 Jan 2021 13:00 online | |
| Tues 19 Jan 2021 13:00 online | Meirav Zehavi (Ben Gurion) Approximate Counting of k-Paths Given a directed or undirected graph G, the k-Path problem is to decide whether G contains a simple path on k vertices, called a k-path. In its counting version, the objective is to count the number of k-paths. Both decision and counting versions have been extensively studied from the viewpoint of Parameterized Complexity. While the counting version is #W[1]-hard (thus unlikely to be in FPT), it admits an FPT-approximation scheme. In this talk, I will discuss two such FPT-approximation schemes that are state-of-the-art in this regard. |
| Tues 26 Jan 2021 13:00 online | Elisheva Shamash (Technion) Principal-Agent VCG Contracts We study a complete information game with multiple principals and multiple common agents. Each agent takes an action that can affect the payoffs of all principals. Prat and Rustichini (Econometrica, 2003) who introduce this model assume first price contracts: each principal offers monetary transfers to each agent conditional on the action taken by the agent. We define VCG contracts in which the monetary transfers to each agent additionally depend on all principals’ offers, and study its effect on the existence of efficient pure subgame perfect equilibrium outcomes. We characterize a necessary and sufficient condition for the existence of a pure subgame perfect equilibrium (SPE) with VCG contracts. As a consequence, we show that the class of instances that admit an efficient SPE with VCG contracts strictly contains the class of instances that admit an efficient SPE with first price contracts, and in fact the difference between these two sets has positive measure. Although VCG contracts broaden the existence of pure subgame perfect equilibria, we show that the worst case welfare loss in a SPE outcome, over all games with any fixed M >2 number of principals, is the same for both VCG contracts and first price contracts. |
| Tues 2 Feb 2021 13:00 online | *** ACiD Meeting *** |
| Tues 9 Feb 2021 13:00 online | Marton Benedek (KRTK, Corvinus) Computing International Kidney Exchange Schemes “In a kidney exchange program, the goal is to find an optimal exchange scheme, where kidney patients swap their donors in order to solve incompatibility issues. We consider international kidney exchange programs, where countries merge their national patient-donor pools in order to maximize social welfare. To encourage full participation, countries that are disadvantaged in some round must receive some compensation for the next round. We study a previously introduced credit system for the case where the kidney exchanges must form a maximum matching. Our results are as follows: 1. We give a polynomial-time algorithm for computing a maximum matching M that approaches a prescribed “fair” target allocation for the countries as close as possible, in the sense that M is lexicographically minimizing the country deviations from the target allocation. 2. We perform a number of computational experiments. These experiments show that combining maximum matchings that are lexicographically minimal with credits for future rounds makes an international KEP significantly more balanced, without decreasing the overall number of transplants in the international pool.” |
| Tues 16 Feb 2021 13:00 online | Hendrik Molter (TU Berlin) Equitable Scheduling on a Single Machine We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least k less than or equal to m days. This corresponds to an equitable schedule where each client is guaranteed a minimal level of service throughout the period of m days. We provide a thorough analysis of the computational complexity of three main variants of this problem, identifying both efficient algorithms and worst-case intractability results. Based on joint work with Klaus Heeger, Danny Hermelin, George B. Mertzios, Rolf Niedermeier, and Dvir Shabtay. |
| Tues 23 Feb 2021 13:00 online | Wanqing Tu (Durham) Efficient Resource Utilisation for Multi-flow Wireless Transmissions In this talk, I will introduce our study on the efficient utilisation of network resources for increasing the number of concurrent multimedia flows when a channel becomes saturated. A new flow scheduling policy is theoretically studied with the motivation of ameliorating the trade-off between limited channel resources and multiple flow transmission. Based on the dynamic states of wireless channels and the profile of multimedia flows, the policy fully utilises the perform gap for increasing the number of performance guaranteed multimedia flows, by scheduling multiple flows in turn without interference. We then study the policy by NS2 simulations, which prove the effectiveness of the flow scheduling policy in increasing the number of concurrent multimedia flows in both single-hop and multi-hop wireless networks. |
| Tues 2 Mar 2021 13:00 online | Igor Carboni Oliveira (Warwick) Extracting computational hardness from learning algorithms I will explain how to obtain hard computational problems from provably correct learning algorithms. These results can be interpreted in different ways. For an optimist, they offer a path to breakthroughs in complexity theory via the discovery of better algorithms. On the other hand, for a pessimist, they might serve as an explanation for the difficulty of designing and analysing learning algorithms. The talk will provide an accessible introduction to this research area and cover some ideas from my recent work with Srinivasan Arunachalam, Alex Grilo, Tom Gur, and Aarthi Sundaram (https://arxiv.org/abs/2012.01920). |
| Tues 9 Mar 2021 13:00 online | Othon Michail (Liverpool) Distributed Computation and Reconfiguration in Actively Dynamic Networks In this talk, motivated by recent advances in the algorithmic theory of dynamic networks, we will discuss systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that, apart from communication, can exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require a global reconfiguration from a given initial network G_s to a target network G_f from a family of networks having some good properties, like small diameter. To formally capture costs associated with creating and maintaining connections, we define three reasonable edge-complexity measures: the total edge activations, the maximum active edges per round, and the maximum degree of a node. We highlight a natural trade-off between time and edge complexity. We give (poly)log(n) time algorithms for transforming any initial connected network G_s into a network G_f of (poly)logarithmic diameter and at the same time electing a unique leader, while minimizing the edge-complexity. We also discuss lower bounds. This novel model of distributed computation and reconfiguration in actively dynamic networks and the proposed measures of the edge complexity of distributed algorithms may open new avenues for research in the algorithmic theory of dynamic networks. At the same time, they may serve as an abstraction of more constrained active-reconfiguration systems, such as reconfigurable robotics which come with geometric constraints, and draw interesting connections with alternative network reconfiguration models, like overlay network construction and network constructors. We discuss several open problems and promising future research directions. This talk is based on a joint work with G. Skretas and P. G. Spirakis which appeared in PODC 2020. |
| Tues 16 Mar 2021 13:00 online | Tereza Klimosova (Charles) On Vizing’s edge colouring question In his 1965 seminal paper on edge colouring, Vizing proved that a (Delta+1)-edge colouring can be reached from any given proper edge colouring through a series of Kempe changes, where Delta is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? In other words, if the graph is Delta-edge-colourable, can we always reach a Delta-edge-colouring? We answer this question in the affirmative for triangle-free graphs. Joint work with Marthe Bonamy, Oscar Defrain, Aurelie Lagoutte and Jonathan Narboni. |