Cseh, Ágnes; Fleiner, Tamás The Complexity of Cake Cutting with Unequal SharesACM Transactions on Algorithms 2020: 1–21
An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this article, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands, which delivers a proportional solution in fewer queries than all known proto- cols. By giving a matching lower bound, we then show that our protocol is asymptotically the fastest possible. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.
Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform ConstraintsAlgorithmica 2020: 3117–3123
In the article "Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints", we claimed a worst-case runtime of \(O(nD \log D)\) and \(O(nD)\) for the Multi-Objective Evolutionary Algorithm and the Multi-Objective \((\mu+(\lambda, \lambda))\) Genetic Algorithm, respectively, on linear profit functions under dynamic uniform constraint, where \(D = |B − B^*|\) denotes the difference between the original constraint bound \(B\) and the new one \(B^*\) . The technique used to prove these results contained an error. We correct this mistake and show a weaker bound of \(O(nD^2)\) for both algorithms instead.
Chauhan, Ankit; Friedrich, Tobias; Rothenberger, Ralf Greed is Good for Deterministic Scale-Free NetworksAlgorithmica 2020: 3338–3389
Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. Therefore, Brach, Cygan, Lacki, and Sankowski [SODA 2016] introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world networks satisfy both deterministic properties and exploit them to design faster algorithms for a number of classical graph problems. We complement the work of Brach et al. by showing that some well-studied random graph models exhibit both the mentioned PLB properties and additionally also a power-law lower bound on the degree distribution (PLB-L). All three properties hold with high probability for Chung-Lu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As a consequence, all results of Brach et al. also hold with high probability or almost surely for those random graph classes. In the second part of this work we study three classical NP-hard combinatorial optimization problems on PLB networks. It is known that on general graphs with maximum degree \(\Delta\), a greedy algorithm, which chooses nodes in the order of their degree, only achieves a \(\Omega(\ln \Delta)\)-approximation for Minimum Vertex Cover and Minimum Dominating Set, and a \(\Omega(\Delta)\)-approximation for Maximum Independent Set. We prove that the PLB-U property suffices for the greedy approach to achieve a constant-factor approximation for all three problems. We also show that all three combinatorial optimization problems are APX-complete even if all PLB-properties holds hence, PTAS cannot be expected unless P=NP.
Ghorbani, Ebrahim; Haemers, Willem H.; Reza Maimani, Hamid; Parsaei Majd, Leila On sign-symmetric signed graphsArs Mathematica Contemporane 2020: 83–93
A signed graph is said to be sign-symmetric if it is switching isomorphic to its negation. Bipartite signed graphs are trivially sign-symmetric. We give new constructions of non-bipartite sign-symmetric signed graphs. Sign-symmetric signed graphs have a symmetric spectrum but not the other way around. We present constructions of signed graphs with symmetric spectra which are not sign-symmetric. This, in particular answers a problem posed by Belardo, Cioab\u{a}, Koolen, and Wang (2018).
Casel, Katrin; Dreier, Jan; Fernau, Henning; Gobbert, Moritz; Kuinke, Philipp; Sanchez Villaamil, Fernando; Schmid, Markus L.; van Leeuwen, Erik Jan Complexity of independency and cliquy treesDiscrete Applied Mathematics 2020: 2–15
An independency (cliquy) tree of an \(n\)-vertex graph \(G\) is a spanning tree of \(G\) in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most \(\ell\) leaves exists parameterized by \(\ell\) are either para-NP- or W[1]-hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is para-NP-hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number \(k\) of internal vertices has an \(O^*(4^k)\)-time algorithm and a \(2k\) vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number \(k\) of internal vertices both have an \(O^*(18^k)\)-time algorithm and an \(O(k\, 2^k)\) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an \(O(3^n f(n))\)-time algorithm to find a spanning tree where the leaf set has a property that can be decided in \(f(n)\) time and has minimum or maximum size.
Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning Domination chain: Characterisation, classical complexity, parameterised complexity and approximabilityDiscrete Applied Mathematics 2020: 23–42
We survey the most important results regarding the domination chain parameters, including the characterisation of the domination sequence, complexity of exact and parameterised algorithms, and approximation and inapproximability ratios. We provide a number of new results for the upper and lower irredundance and their complements, and a few results for other domination chain problems. In particular, we analyse the structure of maximum irredundant sets and we provide new bounds on the upper irredundance number. We show several approximability results for upper and lower irredundance and their complements on general graphs; all four problems remain NP-hard even on planar cubic graphs and APX-hard on cubic graphs. Finally, we give some results on everywhere dense graphs, and study some related extension problems.
Akbari, Saieed; Reza Maimani, Hamid; Parsaei Majd, Leila; Wanless, Ian M. Zero-sum flows for Steiner systemsDiscrete Mathematics 2020: 112074
Abstract. Given a \(t-(v, k, \lambda)\) design, \(D = (X, B)\), a zero-sum \(n\)-flow of \(D\) is a map \(f : \mathcal{B} \longrightarrow \{\pm 1, . . . , \pm (n − 1)\}\) such that for any point \(x \in X\), the sum of \(f\) over all blocks incident with \(x\) is zero. For a positive integer \(k\), we find a zero-sum \(k\)-flow for an STS(uw) and for an \(STS(2v + 7)\) for \(v \equiv 1 (mod 4)\), if there are \(STS(u)\), \(STS(w)\) and \(STS(v)\) such that the \(STS(u)\) and \(STS(v)\) both have a zero-sum \(k\)-flow. In 2015, it was conjectured that for \(v > 7\) every \(STS(v)\) admits a zero-sum 3-flow. Here, it is shown that many cyclic \(STS(v)\) have a zero-sum 3-flow. Also, we investigate the existence of zero-sum flows for some Steiner quadruple systems.
Cseh, Ágnes; Heeger, Klaus The stable marriage problem with ties and restricted edgesDiscrete Optimization 2020: 100571
In the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching. Our computational complexity study targets the existence of a stable solution for each of the three stability definitions, in the presence of each of the three types of restricted pairs. We solve all cases that were still open. As a byproduct, we also derive that the maximum size weakly stable matching problem is hard even in very dense graphs, which may be of independent interest.
Doerr, Benjamin; Krejca, Martin S. Significance-based Estimation-of-Distribution AlgorithmsIEEE Transactions on Evolutionary Computation 2020: 1025–1034
Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that create a probabilistic model of the solution space, which is updated iteratively, based on the quality of the solutions sampled according to the model. As previous works show, this iteration-based perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. In order to overcome this problem, we propose a new EDA based on the classic compact genetic algorithm (cGA) that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based compact genetic algorithm (sig-cGA) optimizes the commonly regarded benchmark functions OneMax, LeadingOnes, and BinVal all in quasilinear time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA – an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model – we prove that it optimizes OneMax only in a time exponential in its hypothetical population size. Similarly, we show that the convex search algorithm cannot optimize OneMax in polynomial time.
Alizadeh, Faezeh; Maimani, Hamid Reza; Parsaei Majd, Leila; Rajabi Parsa, Mina Roman {2}-domination in graphs and graph productsIranian Journal of Mathematical Sciences and Informatics Iranian Journal of Mathematical Sciences and Informatics 2020
For a graph \(G = (V, E)\) of order n, a Roman {2}-dominating function \(f : V \to \{0, 1, 2\}\) has the property that for every vertex \(v \in V\) with \(f(v) = 0\), either \(v\) is adjacent to a vertex assigned 2 under \(f\) , or \(v\) is adjacent to at least two vertices assigned 1 under \(f\). In this paper, we classify all graphs with Roman {2}-domination number belonging to the set \(\{2, 3, 4, n - 2, n - 1, n\}\). Furthermore, we obtain some results about Roman {2}-domination number of some graph operations.
Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton Hyperbolic Embeddings for Near-Optimal Greedy RoutingJournal of Experimental Algorithmics (JEA) 2020: 1–18
Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular, our embeddings guarantee that greedy routing always succeeds in reaching the target, and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real-world networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results (i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths). In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention. In addition to measuring the stretch, we empirically evaluate our algorithms regarding the size of the coordinates of the resulting embeddings and observe how it impacts the success rate when coordinates are not represented with very high precision. Since numerical difficulties are a major issue when performing computations in the hyperbolic plane, we consider variations of our algorithm that improve the success rate when using coordinates with lower precision.
Birnick, Johann; Bläsius, Thomas; Friedrich, Tobias; Naumann, Felix; Papenbrock, Thorsten; Schirneck, Martin Hitting Set Enumeration with Partial Information for Unique Column Combination DiscoveryProceedings of the VLDB Endowment 2020: 2270–2283
Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations. In this paper, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs. In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.
Battaglia, Francesco; Cucina, Domenico; Rizzo, Manuel Parsimonious periodic autoregressive models for time series with evolving trend and seasonalityStatistics and Computing 2020: 77–91
This paper proposes an extension of Periodic AutoRegressive (PAR) modelling for time series with evolving features. The large scale of modern datasets, in fact, implies that the time span may subtend several evolving patterns of the underlying series, affecting also seasonality. The proposed model allows several regimes in time and a possibly different PAR process with a trend term in each regime. The means, autocorrelations and residual variances may change both with the regime and the season, resulting in a very large number of parameters. Therefore as a second step we propose a grouping procedure on the PAR parameters, in order to obtain a more parsimonious and concise model. The model selection procedure is a complex combinatorial problem, and it is solved basing on Genetic Algorithms that optimize an information criterion. The model is tested in both simulation studies and real data analysis from different fields, proving to be effective for a wide range of series with evolving features, and competitive with respect to more specific models.
Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, Martin Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear ConstraintsTheoretical Computer Science 2020: 3–19
Linear functions have gained great attention in the run time analysis of evolutionary computation methods. The corresponding investigations have provided many effective tools for analyzing more complex problems. So far, the runtime analysis of evolutionary algorithms has mainly focused on unconstrained problems, but problems occurring in applications frequently involve constraints. Therefore, there is a strong need to extend the methods for analyzing unconstrained problems to a setting involving constraints. In this paper, we consider the behavior of the classical (1+1) evolutionary algorithm on linear functions under linear constraint. We show tight bounds in the case where the constraint is given by the OneMax function and the objective function is given by either the OneMax or the BinVal function. For the general case we present upper and lower bounds.
Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes; Melnichenko, Anna Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programmingTheoretical Computer Science 2020: 96–113
For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation: the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts); and also the role and the realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had surprisingly little share in this work. We analyze a simple crossover operator in combination with randomized local search, where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); we denote the resulting algorithm Concatenation Crossover GP. We consider three variants of the well-studied Majority test function, adding large plateaus in different ways to the fitness landscape and thus giving a test bed for analyzing the interplay of variation operators and bloat control mechanisms in a setting with local optima. We show that the Concatenation Crossover GP can efficiently optimize these test functions, while local search cannot be efficient for all three variants independent of employing bloat control.
Krejca, Martin S.; Witt, Carsten Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMaxTheoretical Computer Science 2020: 143–165
The Univariate Marginal Distribution Algorithm (UMDA) -- a popular estimation-of-distribution algorithm -- is studied from a run time perspective. On the classical OneMax benchmark function on bit strings of length \(n\), a lower bound of \(\Omega(\lambda + \mu \sqrt{n} + n\log n)\), where \(\mu\) and \(\lambda\) are algorithm-specific parameters, on its expected run time is proved. This is the first direct lower bound on the run time of UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation-of-distribution algorithms in general.
Doerr, Benjamin; Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run timeTheoretical Computer Science 2020: 144–168
While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat, that is, the unnecessary growth of solution lengths, which may slow down the optimization process. So far, the mathematical runtime analysis could not deal well with bloat and required explicit assumptions limiting bloat. In this paper, we provide the first mathematical runtime analysis of a GP algorithm that does not require any assumptions on the bloat. Previous performance guarantees were only proven conditionally for runs in which no strong bloat occurs. Together with improved analyses for the case with bloat restrictions our results show that such assumptions on the bloat are not necessary and that the algorithm is efficient without explicit bloat control mechanism. More specifically, we analyzed the performance of the \((1+1)\) GP on the two benchmark functions Order and Majority. When using lexicographic parsimony pressure as bloat control, we show a tight runtime estimate of \(O(T_{init}+n \log n)\) iterations both for Order and Majority. For the case without bloat control, the bounds \(O(T_{init} \log T_{init} + n (\log n)^3)\) and \(\Omega(T_{init} + n \log n)\) (and \(\Omega (T_{init} + \log T_{init})\) for \(n=1\)) hold for Majority.
Bil{ò}, Davide; Lenzner, Pascal On the Tree Conjecture for the Network Creation GameTheory of Computing Systems 2020: 422–443
Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. (2003) is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of $\alpha$ per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all $\alpha$ and that for $\alpha \geq n$ all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price $\alpha$ and employ it to improve on the best known bound for the latter conjecture. In particular we show that for $\alpha>4n −13$ all equilibrium networks must be trees, which implies a constant price of anarchy for this range of $\alpha$. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.
Krejca, Martin S.; Witt, Carsten Theory of Estimation-of-Distribution AlgorithmsTheory of Evolutionary Computation: Recent Developments in Discrete Optimization 2020: 405–442
Estimation-of-distribution algorithms (EDAs) are general metaheuristics used in optimization that represent a more recent alternative to classical approaches such as evolutionary algorithms. In a nutshell, EDAs typically do not directly evolve populations of search points but build probabilistic models of promising solutions by repeatedly sampling and selecting points from the underlying search space. Recently, significant progress has been made in the theoretical understanding of EDAs. This chapter provides an up-to-date overview of the most commonly analyzed EDAs and the most recent theoretical results in this area. In particular, emphasis is put on the runtime analysis of simple univariate EDAs, including a description of typical benchmark functions and tools for the analysis. Along the way, open problems and directions for future research are described.
Doskoč, Vanja; Kötzing, Timo Cautious Limit LearningAlgorithmic Learning Theory (ALT) 2020: 251–276
We investigate language learning in the limit from text with various \(\mathit{cautious}\) learning restrictions. Learning is \(\mathit{cautious}\) if no hypothesis is a proper subset of a previous guess. While dealing with a seemingly natural learning behaviour, cautious learning does severely restrict explanatory (syntactic) learning power. To further understand why exactly this loss of learning power arises, Kötzing and Palenta (2016) introduced weakened versions of cautious learning and gave first partial results on their relation. In this paper, we aim to understand the restriction of cautious learning more fully. To this end we compare the known variants in a number of different settings, namely full-information and (partially) set-driven learning, paired either with the syntactic convergence restriction (explanatory learning) or the semantic convergence restriction (behaviourally correct learning). To do so, we make use of normal forms presented in Kötzing et al. (2017), most notably strongly locking and consistent learning. While strongly locking learners have been exploited when dealing with a variety of syntactic learning restrictions, we show how they can be beneficial in the semantic case as well. Furthermore, we expand the normal forms to a broader range of learning restrictions, including an answer to the open question of whether cautious learners can be assumed to be consistent, as stated in Kötzing et al. (2017).
Das, Syamantak; Jain, Lavina; Kumar, Nikhil A Constant Factor Approximation for Capacitated Min-Max Tree CoverApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 2020: 55:1–55:13
Given a graph \(G=(V,E)\) with non-negative real edge lengths and an integer parameter \(k\), the (uncapacitated) Min-Max Tree Cover problem seeks to find a set of at most \(k\) trees which together span \(V\) and each tree is a subgraph of \(G\). The objective is to minimize the maximum length among all the trees. In this paper, we consider a capacitated generalization of the above and give the first constant factor approximation algorithm. In the capacitated version, there is a hard uniform capacity (\(\lambda\)) on the number of vertices a tree can cover. Our result extends to the rooted version of the problem, where we are given a set of \(k\) root vertices, \(R\) and each of the covering trees is required to include a distinct vertex in \(R\) as the root. Prior to our work, the only result known was a \((2k-1)\)-approximation algorithm for the special case when the total number of vertices in the graph is \(k\lambda\) [Guttmann-Beck and Hassin, J. of Algorithms, 1997]. Our technique circumvents the difficulty of using the minimum spanning tree of the graph as a lower bound, which is standard for the uncapacitated version of the problem [Even et al., OR Letters 2004],[Khani et al., Algorithmica 2010]. Instead, we use Steiner trees that cover \(\lambda\) vertices along with an iterative refinement procedure that ensures that the output trees have low cost and the vertices are well distributed among the trees.
Bläsius, Thomas; Böther, Maximilian; Fischbeck, Philipp; Friedrich, Tobias; Gries, Alina; Hüffner, Falk; Kißig, Otto; Lenzner, Pascal; Molitor, Louise; Schiller, Leon; Wells, Armin; Wietheger, Simon A Strategic Routing Framework and Algorithms for Computing Alternative PathsAlgorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1–10:14
Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to higher overall and individual travel times. In contrast, strategic routing aims at optimizing the traffic for all agents regarding a global optimization goal. We introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them, which we call Single Alternative Path (SAP), in detail. There, we are given an original route between a single origin–destination pair. The goal is to suggest an alternative route to all agents that optimizes the overall travel time under the assumption that the agents distribute among both routes according to a psychological model, for which we introduce the concept of Pareto-conformity. We show that the SAP problem is NP-complete, even for such models. Nonetheless, assuming Pareto-conformity, we give multiple algorithms for different variants of SAP, using multi-criteria shortest path algorithms as subroutines.Moreover, we prove that several natural models are in fact Pareto-conform. The implementation and evaluation of our algorithms serve as a proof of concept, showing that SAP can be solved in reasonable time even though the algorithms have exponential running time in the worst case.
Fogel, Sharon; Averbuch-Elor, Hadar; Cohen, Sarel; Mazor, Shai; Litman, Roee ScrabbleGAN: Semi-Supervised Varying Length Handwritten Text GenerationConference on Computer Vision and Pattern Recognition (CVPR) 2020: 4323–4332
Optical character recognition (OCR) systems performance have improved significantly in the deep learning era. This is especially true for handwritten text recognition (HTR), where each author has a unique style, unlike printed text, where the variation is smaller by design. That said, deep learning based HTR is limited, as in every other task, by the number of training examples. Gathering data is a challenging and costly task, and even more so, the labeling task that follows, of which we focus here. One possible approach to reduce the burden of data annotation is semi-supervised learning. Semi supervised methods use, in addition to labeled data, some unlabeled samples to improve performance, compared to fully supervised ones. Consequently, such methods may adapt to unseen images during test time. We present ScrabbleGAN, a semi-supervised approach to synthesize handwritten text images that are versatile both in style and lexicon. ScrabbleGAN relies on a novel generative model which can generate images of words with an arbitrary length. We show how to operate our approach in a semi-supervised manner, enjoying the aforementioned benefits such as performance boost over state of the art supervised HTR. Furthermore, our generator can manipulate the resulting text style. This allows us to change, for instance, whether the text is cursive, or how thin is the pen stroke.
Doskoč, Vanja; Friedrich, Tobias; Göbel, Andreas; Neumann, Aneta; Neumann, Frank; Quinzan, Francesco Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic SettingsEuropean Conference on Artificial Intelligence (ECAI) 2020: 435–442
We study the problem of maximizing a non-monotone submodular function under multiple knapsack constraints. We propose a simple discrete greedy algorithm to approach this problem, and prove that it yields strong approximation guarantees for functions with bounded curvature. In contrast to other heuristics, this does not require problem relaxation to continuous domains and it maintains a constant-factor approximation guarantee in the problem size. In the case of a single knapsack, our analysis suggests that the standard greedy can be used in non-monotone settings. Additionally, we study this problem in a dynamic setting, in which knapsacks change during the optimization process. We modify our greedy algorithm to avoid a complete restart at each constraint update. This modification retains the approximation guarantees of the static case. We evaluate our results experimentally on a video summarization and sensor placement task. We show that our proposed algorithm competes with the state-of-the-art in static settings. Furthermore, we show that in dynamic settings with tight computational time budget, our modified greedy yields significant improvements over starting the greedy from scratch, in terms of the solution quality achieved.
Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin The Minimization of Random HypergraphsEuropean Symposium on Algorithms (ESA) 2020: 21:1–21:15
We investigate the maximum-entropy model \(\mathcal{B}_{n,m,p}\) for random \(n\)-vertex, \(m\)-edge multi-hypergraphs with expected edge size \(pn\). We show that the expected size of the minimization \(\min(\mathcal{B}_{n,m,p})\), i.e., the number of inclusion-wise minimal edges of \(\mathcal{B}_{n,m,p}\), undergoes a phase transition with respect to \(m\). If \(m\) is at most \(1/(1-p)^{(1-p)n}\), then \(\mathrm{E}[|\min(\mathcal{B}_{n,m,p})|]\) is of order \(\Theta(m)\), while for \(m \ge 1/(1-p)^{(1-p+\varepsilon)n}\) for any \(\varepsilon > 0\), it is \(\Theta( 2^{(\mathrm{H}(\alpha) + (1-\alpha) \log_2 p) n}/ \sqrt{n})\). Here, \(\mathrm{H}\) denotes the binary entropy function and \(\alpha = - (\log_{1-p} m)/n\). The result implies that the maximum expected number of minimal edges over all \(m\) is \(\Theta((1+p)^n/\sqrt{n})\). Our structural findings have algorithmic implications for minimizing an input hypergraph. This has applications in the profiling of relational databases as well as for the Orthogonal Vectors problem studied in fine-grained complexity. We make several technical contributions that are of independent interest in probability. First, we improve the Chernoff--Hoeffding theorem on the tail of the binomial distribution. In detail, we show that for a binomial variable \(Y \sim \mathrm{Bin}(n,p)\) and any \(0 < x < p\), it holds that \(\mathrm{P}[Y \le xn] = \Theta( 2^{-\!\mathrm{D}(x \,{\|}\, p) n}/\sqrt{n})\), where \(\mathrm{D}\) is the binary Kullback--Leibler divergence between Bernoulli distributions. We give explicit upper and lower bounds on the constants hidden in the big-O notation that hold for all \(n\). Secondly, we establish the fact that the probability of a set of cardinality \(i\) being minimal after \(m\) i.i.d. maximum-entropy trials exhibits a sharp threshold behavior at \(i^* = n + \log_{1-p} m\).
Garg, Naveen; Kumar, Nikhil Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral FlowEuropean Symposium on Algorithms (ESA) 2020: 55:1–55:13
Given an edge weighted graph and a forest \(F\), the {\em 2-edge connectivity augmentation problem} is to pick a minimum weighted set of edges, \(E'\), such that every connected component of \(E'\cup F\) is 2-edge connected. Williamson et al. gave a 2-approximation algorithm (WGMV) for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be modified to obtain a half-integral dual. The 2-edge connectivity augmentation problem has an interesting connection to routing flow in graphs where the union of supply and demand is planar. The half-integrality of the dual leads to a tight 2-approximate max-half-integral-flow min-multicut theorem.
Doerr, Benjamin; Krejca, Martin S. The Univariate Marginal Distribution Algorithm Copes Well with Deception and EpistasisEvolutionary Computation in Combinatorial Optimization (EvoCOP) 2020: 51–66
Best-Paper Award
Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna; Molitor, Louise Fair Tree Connection Games with Topology-Dependent Edge CostFoundations of Software Technology and Theoretical Computer Science (FSTTCS) 2020: 15:1–15:15
How do rational agents self-organize when trying to connect to a common target? We study this question with a simple tree formation game which is related to the well-known fair single-source connection game by Anshelevich et al.(FOCS'04) and selfish spanning tree games by Gourvès and Monnot (WINE'08). In our game agents correspond to nodes in a network that activate a single outgoing edge to connect to the common target node (possibly via other nodes). Agents pay for their path to the common target, and edge costs are shared fairly among all agents using an edge. The main novelty of our model is dynamic edge costs that depend on the in-degree of the respective endpoint. This reflects that connecting to popular nodes that have increased internal coordination costs is more expensive since they can charge higher prices for their routing service. In contrast to related models, we show that equilibria are not guaranteed to exist, but we prove the existence for infinitely many numbers of agents. Moreover, we analyze the structure of equilibrium trees and employ these insights to prove a constant upper bound on the Price of Anarchy as well as non-trivial lower bounds on both the Price of Anarchy and the Price of Stability. We also show that in comparison with the social optimum tree the overall cost of an equilibrium tree is more fairly shared among the agents. Thus, we prove that self-organization of rational agents yields on average only slightly higher cost per agent compared to the centralized optimum, and at the same time, it induces a more fair cost distribution. Moreover, equilibrium trees achieve a beneficial trade-off between a low height and low maximum degree, and hence these trees might be of independent interest from a combinatorics point-of-view. We conclude with a discussion of promising extensions of our model.
Doerr, Benjamin; Krejca, Martin S. Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of OptimaGenetic and Evolutionary Computation Conference (GECCO) 2020: 796–804
Finding a large set of optima in a multimodal optimization landscape is a challenging task. Classical population-based evolutionary algorithms (EAs) typically converge only to a single solution. While this can be counteracted by applying niching strategies, the number of optima is nonetheless trivially bounded by the population size. Estimation-of-distribution algorithms (EDAs) provide an alternative approach by maintaining a probabilistic model of the solution space instead of an explicit population. Such a model has the benefit of being able to implicitly represent a solution set that is far larger than any realistic population size. To support the study of how optimization algorithms handle large sets of optima, we propose the test function EqualBlocksOneMax (EBOM). It has an easy to optimize fitness landscape, however, with an exponential number of optima. We show that the bivariate EDA mutual-information-maximizing input clustering (MIMIC), without any problem-specific modification, quickly generates a model that behaves very similarly to a theoretically ideal model for that function, which samples each of the exponentially many optima with the same maximal probability.
Bossek, Jakob; Casel, Katrin; Kerschke, Pascal; Neumann, Frank The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search HeuristicsGenetic and Evolutionary Computation Conference (GECCO) 2020: 1286–1294
Several important optimization problems in the area of vehicle routing can be seen as a variant of the classical Traveling Salesperson Problem (TSP). In the area of evolutionary computation, the traveling thief problem (TTP) has gained increasing interest over the last 5 years. In this paper, we investigate the effect of weights on such problems, in the sense that the cost of traveling increases with respect to the weights of nodes already visited during a tour. This provides abstractions of important TSP variants such as the Traveling Thief Problem and time dependent TSP variants, and allows to study precisely the increase in difficulty caused by weight dependence. We provide a 3.59-approximation for this weight dependent version of TSP with metric distances and bounded positive weights. Furthermore, we conduct experimental investigations for simple randomized local search with classical mutation operators and two variants of the state-of-the-art evolutionary algorithm EAX adapted to the weighted TSP. Our results show the impact of the node weights on the position of the nodes in the resulting tour.
Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rizzo, Manuel; Zahn, Arthur Memetic Genetic Algorithms for Time Series Compression by Piecewise Linear ApproximationInternational Conference on Neural Information Processing (ICONIP) 2020: 592–604
Time series are sequences of data indexed by time. Such data are collected in various domains, often in massive amounts, such that storing them proves challenging. Thus, time series are commonly stored in a compressed format. An important compression approach is piecewise linear approximation (PLA), which only keeps a small set of time points and interpolates the remainder linearly. Picking a subset of time points such that the PLA minimizes the mean squared error to the original time series is a challenging task, naturally lending itself to heuristics. We propose the piecewise linear approximation genetic algorithm (PLA-GA) for compressing time series by PLA. The PLA-GA is a memetic \((\mu + \lambda)\) GA that makes use of two distinct operators tailored to time series compression. First, we add special individuals to the initial population that are derived using established PLA heuristics. Second, we propose a novel local search operator that greedily improves a compressed time series. We compare the PLA-GA empirically with existing evolutionary approaches and with a deterministic PLA algorithm, known as Bellman's algorithm, that is optimal for the restricted setting of sampling. In both cases, the PLA-GA approximates the original time series better and quicker. Further, it drastically outperforms Bellman's algorithm with increasing instance size with respect to run time until finding a solution of equal or better quality -- we observe speed-up factors between 7 and 100 for instances of 90,000 to 100,000 data points.
Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna Flow-Based Network Creation GamesInternational Joint Conference on Artificial Intelligence (IJCAI) 2020: 139–145
Network Creation Games (NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like VoIP. However, with today's abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufficient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selfish agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network flow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is~1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.
Garg, Naveen; Kumar, Nikhil; Sebö, András Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-ApproximationInteger Programming and Combinatorial Optimization (IPCO) 2020: 144–157
In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. We consider instances where the union of the supply and demand graphs is planar and prove that there exists a multiflow of value at least half the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer flow of value at least half the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing at most half the value thus providing a 1/4-approximation algorithm and integrality gap for maximum integer multiflows in the plane.
Feldmann, Andreas; Issac, Davis; Rai, Ashutosh Fixed-Parameter Tractability of the Weighted Edge Clique Partition ProblemInternational Symposium on Parameterized and Exact Computation (IPEC) 2020: 1–16
We develop an FPT algorithm and a bi-kernel for the Weighted Edge Clique Partition (WECP) problem, where a graph with \(n\) vertices and integer edge weights is given together with an integer \(k\), and the aim is to find \(k\) cliques, such that every edge appears in exactly as many cliques as its weight. The problem has been previously only studied in the unweighted version called Edge Clique Partition (ECP), where the edges need to be partitioned into \(k\) cliques. It was shown that ECP admits a kernel with \(k^2\) vertices [Mujuni and Rosamond, 2008], but this kernel does not extend to WECP. The previously fastest algorithm known for ECP has a runtime of \( 2^{O(k^2)}\) \(n^{O(1)}\) [Issac, 2019]. For WECP we develop a bi-kernel with \(4^k\) vertices, and an algorithm with runtime \(2^{O(k^{3/2}w^{1/2}\log(k/w))} n^{O(1)}\), where \(w\) is the maximum edge weight. The latter in particular improves the runtime for ECP to \(2^{O(k^{3/2}\log k)} n^{O(1)}\).
Kumar, Nikhil Multicommodity Flows in Planar Graphs with Demands on FacesInternational Symposium on Algorithms and Computation (ISAAC) 2020: 1–11
We consider the problem of multicommodity flows in planar graphs. Seymour showed that if the union of supply and demand graphs is planar, then the cut condition is also sufficient for routing demands. Okamura-Seymour showed that if the supply graph is planar and all demands are incident on one face, then again the cut condition is sufficient for routing demands. We consider a common generalization of these settings where the end points of each demand are on the same face of the planar graph. We show that if the source sink pairs on each face of the graph are such that sources and sinks appear contiguously on the cycle bounding the face, then the flow cut gap is at most 3. We come up with a notion of approximating demands on a face by convex combination of laminar demands to prove this result.
Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise Topological Influence and Locality in Swap Schelling GamesInternational Symposium on Mathematical Foundations of Computer Science (MFCS) 2020: 15:1–15:15
Residential segregation is a wide-spread phenomenon that can be observed in almost everymajor city. In these urban areas residents with different racial or socioeconomic backgroundtend to form homogeneous clusters. Schelling’s famous agent-based model for residentialsegregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slightbias towards agents preferring similar neighbors. Very recently, Schelling’s model has beeninvestigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight boundson the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, whichare commonly used in empirical studies. For grids we also show that locality has a severeimpact on the game dynamics.
Michail, Othon; Skretas, George; Spirakis, G. Paul Distributed Computation and Reconfiguration in Actively Dynamic NetworksPrinciples of Distributed Computing (PODC) 2020: 448–457
In this paper, motivated by recent advances in the algorithmic theory of dynamic networks, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also 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. With reasonably powerful computational entities, there is a straightforward algorithm that transforms any \(G_s\) into a spanning clique in \( \mathcal{O} (\log n) \) time, where time is measured in synchronous rounds and n is the number of entities. From the clique, the algorithm can then compute any global function on inputs and reconfigure to any desired target network in one additional round. We argue that such a strategy, while time-optimal, is impractical for real applications. In real dynamic networks there is typically a cost associated with creating and maintaining connections. To formally capture such costs, we define three reasonable edge-complexity measures: the total edge activations, the maximum activated edges per round, and the maximum activated degree of a node. The clique formation strategy highlighted above, maximizes all of them. We aim at improved algorithms that will achieve (poly)\(log(n)\) time while minimizing the edge-complexity for the general task of transforming any \(G_s\) into a \(G_f\) of diameter (poly)\(\log(n)\). There is a natural trade-off between time and edge complexity. Our main lower bound shows that \(\Omega(n)\) total edge activations and \(\Omega(n/\log n)\) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of \(\Theta(\log n)\) rounds. On the positive side, we give three distributed algorithms for our general task. The first runs in \(\mathcal{O}(log n)\) time, with at most \(2n\) active edges per round, an optimal total of \(\mathcal{O}(n \log n)\) edge activations, a maximum degree \(n −1\), and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations, that is, \(\mathcal{O}(\log^2 n)\) and \(\mathcal{O}(n \log^2 n)\), respectively. It gives a target network of diameter \(\mathcal{O}(\log n)\) and uses \(\mathcal{O}(n)\) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog(n) then we can achieve a running time of \(\mathcal{o}(\log^2 n)\). 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.
Kötzing, Timo; Witt, Carsten Improved Fixed-Budget Results via Drift AnalysisParallel Problem Solving From Nature (PPSN) 2020: 648–660
Fixed-budget theory is concerned with computing or bounding the fitness value achievable by randomized search heuristics within a given budget of fitness function evaluations. Despite recent progress in fixed-budget theory, there is a lack of general tools to derive such results. We transfer drift theory, the key tool to derive expected optimization times, to the fixed-budged perspective. A first and easy-to-use statement concerned with iterating drift in so-called greed-admitting scenarios immediately translates into bounds on the expected function value. Afterwards, we consider a more general tool based on the well-known variable drift theorem. Applications of this technique to the LeadingOnes benchmark function yield statements that are more precise than the previous state of the art.
Antoniadis, Antonios; Garg, Naveen; Kumar, Gunjan; Kumar, Nikhil Parallel Machine Scheduling to Minimize Energy ConsumptionSymposium on Discrete Algorithms (SODA) 2020: 2758–2769
Given \(n\) jobs with release dates, deadlines and processing times we consider the problem of scheduling them on \(m\) parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires \(L\) units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem.
Feldmann, Michael; Khazraei, Ardalan; Scheideler, Christian Time- and Space-Optimal Clock Synchronization in the Beeping ModelSymposium Parallelism in Algorithms and Architectures (SPAA) 2020: 223–233
We consider the clock synchronization problem in the (discrete) beeping model: Given a network of \(n\) nodes with each node having a clock value \(\delta(v) \in\) \(\{ 0,\ldots , T-1\}\), the goal is to synchronize the clock values of all nodes such that they have the same value in any round. As is standard in clock synchronization, we assume arbitrary activations for all nodes, i.e., the nodes start their protocol at an arbitrary round (not limited to \(\{0,\ldots,T-1\}\)). We give an asymptotically optimal algorithm that runs in \( 4D + \lfloor D/\lfloor T/4 \rfloor \rfloor \cdot\ \)\((T \mod 4) = O(D)\) rounds, where \(D\) is the diameter of the network. Once all nodes are in sync, they beep at the same round every \(T\) rounds. The algorithm drastically improves on the \(O(T D)\)-bound of [Alistarh et al. 2013] (where \(T\) is required to be at least \(4n\), so the bound is no better than \(O(nD)\)). Our algorithm is very simple as nodes only have to maintain \(3\) bits in addition to the \(\lceil \log T \rceil\) bits needed to maintain the clock. Furthermore we investigate the complexity of self-stabilizing solutions for the clock synchronization problem: We first show lower bounds of \(\Omega(\max\{T,n\})\) rounds on the runtime and \(\Omega(\log(\max\{T,n\}))\) bits of memory required for any such protocol. Afterwards we present a protocol that runs in \(O(\max\{T,n\})\) rounds using at most \(O(\log(\max\{T,n\}))\) bits at each node, which is asymptotically optimal with regards to both, runtime and memory requirements.
Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian Solving Vertex Cover in Polynomial Time on Hyperbolic Random GraphsSymposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1–25:14
The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. Similarly, greedy algorithms deliver very good approximations to the optimal solution in practice. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that, on real instances, this leads to better approximations than the standard greedy approach within reasonable time. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that this leads to even better approximations than the standard greedy approach on real instances.
Chechik, Shiri; Cohen, Sarel Distance sensitivity oracles with subcubic preprocessing time and fast query timeSymposium Theory of Computing (STOC) 2020: 1375–1388
We present the first distance sensitivity oracle (DSO) with subcubic preprocessing time and poly-logarithmic query time for directed graphs with integer weights in the range \([−M,M]\). Weimann and Yuster [FOCS 10] presented a distance sensitivity oracle for a single vertex/edge failure with subcubic preprocessing time of \(\mathcal{O}(Mn^{\omega+1− \alpha})\) and subquadratic query time of \(\tilde{\mathcal{O}}(n^{1+\alpha})\), where \(\alpha\) is any parameter in \([0,1]\), \(n\) is the number of vertices, \(m\) is the number of edges, the \(\tilde{\mathcal{O}}(·)\) notation hides poly-logarithmic factors in \(n\) and \(\omega<2.373\) is the matrix multiplication exponent.Later, Grandoni and Vassilevska Williams [FOCS 12] substantially improved the query time to sublinear in \(n\). In particular, they presented a distance sensitivity oracle for a single vertex/edge failure with \(\tilde{\mathcal{O}}\)\( (Mn^{\omega +1/2}\) \(+ Mn^{\omega+\alpha(4−\omega)})\) preprocessing time and \(\tilde{\mathcal{O}}(n^{1−\alpha})\) query time. Despite the substantial improvement in the query time, it still remains polynomial in the size of the graph, which may be undesirable in many settings where the graph is of large scale. A natural question is whether one can hope for a distance sensitivity oracle with subcubic preprocessing time and very fast query time (of poly-logarithmic in \(n\)). In this paper we answer this question affirmatively by presenting a distance sensitive oracle supporting a single vertex/edge failure in subcubic \(\tilde{\mathcal{O}}(Mn^{2.873})\) preprocessing time for \(\omega=2.373\), \(\tilde{\mathcal{O}}(n^{2.5})\) space and near optimal query time of \(\tilde{\mathcal{O}}(1)\). For comparison, with the same \(\tilde{\mathcal{O}}(Mn^{2.873})\) preprocessing time the DSO of Grandoni and Vassilevska Williams has \(\tilde{\mathcal{O}}(n^{0.693})\) query time. In fact, the best query time their algorithm can obtain is \(\tilde{\mathcal{O}}(Mn^{0.385})\) (with \(\tilde{\mathcal{O}}(Mn^3)\) preprocessing time).
Becher, Kilian; Lagodzinski, J. A. Gregor; Strufe, Thorsten Privacy-Preserving Public Verification of Ethical Cobalt SourcingTrust, Security and Privacy in Computing and Communications (TrustCom) 2020: 998–1005
Cobalt is a key ingredient of lithium-ion batteries and therefore is crucial for many modern devices. To ensure ethical sourcing, consumers need a way to verify provenance of their cobalt-based products, including the percentage of artisanally mined (ASM) cobalt. Existing frameworks for provenance and supply chain traceability rely on distributed ledgers. Providing public verifiability via permissionless distributed ledgers is trivial. However, offering public verifiability based on confidential production details seems contradictory. Hence, existing frameworks lack public verifiability of ratios between commodities while ensuring confidentiality of supply chain details. We propose a protocol that allows end consumers to verify the percentage of ASM cobalt in their products. Unlike previous solutions, production details are published and processed entirely in encrypted form by employing homomorphic encryption and proxy re-encryption. Thus, it ensures a high level of confidentiality of supply chain data. It has constant consumer-side complexity, making it suitable for mobile devices.
Held, Stephan; Khazraei, Ardalan An Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree ProblemWorkshop on Approximation and Online Algorithms (WAOA) 2020: 189–203
The cost-distance Steiner tree problem asks for a Steiner tree in a graph that minimizes the total cost plus a weighted sum of path delays from the root to the sinks. We present an improved approximation for the uniform cost-distance Steiner tree problem, where the delay of a path corresponds to the sum of edge costs along that path. Previous approaches deploy a bicriteria approximation algorithm for the length-bounded variant that does not take the actual delay weights into account. Our algorithm modifies a similar algorithm for the single-sink buy-at-bulk problem by Guha et al. [2009], allowing a better approximation factor for our problem. In contrast to the bicriteria algorithms it considers delay weights explicitly. Thereby, we achieve an approximation factor of (1+ \(\beta\) ), where \(\beta\) is the approximation factor for the Steiner tree problem. This improves the previously best known approximation factor for the uniform cost-distance Steiner tree problem from 2:87 to 2:39. This algorithm can be extended to the problem where the ratio of edge costs to edge delays throughout the graph is bounded from above and below. In particular, this shows that a previous inapproximability result (Chuzhoy et al. [2008]) requires large variations between edge delays and costs. Finally, we present an important application of our new algorithm in chip design. The cost-distance Steiner tree problem occurs as a Lagrangean subproblem when optimizing millions of Steiner trees with mutually depending path length bounds. We show how to quickly approximate a continuous relaxation of this problem with our new algorithm.
Khazraei, Ardalan; Kötzing, Timo; Seidel, Karen Learning Half-Spaces and other Concept Classes in the Limit with Iterative LearnersCoRR 2020
ArXiv preprint
In order to model an efficient learning paradigm, iterative learning algorithms access data one by one, updating the current hypothesis without regress to past data. Past research on iterative learning analyzed for example many important additional requirements and their impact on iterative learners. In this paper, our results are twofold. First, we analyze the relative learning power of various settings of iterative learning, including learning from text and from informant, as well as various further restrictions, for example we show that strongly non-U-shaped learning is restrictive for iterative learning from informant. Second, we investigate the learnability of the concept class of half-spaces and provide a constructive iterative algorithm to learn the set of half-spaces from informant.
Kötzing, Timo; Seidel, Karen Learning Languages in the Limit from Positive Information with Finitely Many Memory ChangesCoRR 2020
ArXiv preprint
We investigate learning collections of languages from texts by an inductive inference machine with access to the current datum and its memory in form of states. The bounded memory states (\(BMS\)) learner is considered successful in case it eventually settles on a correct hypothesis while exploiting only finitely many different states. We give the complete map of all pairwise relations for an established collection of learning success restrictions. Most prominently, we show that non-U-shapedness is not restrictive, while conservativeness and (strong) monotonicity are. Some results carry over from iterative learning by a general lemma showing that, for a wealth of restrictions (the semantic restrictions), iterative and bounded memory states learning are equivalent. We also give an example of a non-semantic restriction (strongly non-U-shapedness) where the two settings differ.
