
Anand, S.; Bringmann, Karl; Friedrich, Tobias; Garg, Naveen; Kumar, Amit Minimizing Maximum (Weighted) FlowTime on Related and Unrelated Machines. International Colloquium on Automata, Languages and Programming (ICALP) 2013: 1324
In this paper we initiate the study of job scheduling on related and unrelated machines so as to minimize the maximum flow time or the maximum weighted flow time (when each job has an associated weight). Previous work for these metrics considered only the setting of parallel machines, while previous work for scheduling on unrelated machines only considered \(L_p, p < \infty\) norms. Our main results are: (1) we give an \(O(\epsilon^{3})\)competitive algorithm to minimize maximum weighted flow time on related machines where we assume that the machines of the online algorithm can process \(1+\epsilon\) units of a job in 1 timeunit (\(\epsilon\) speed augmentation). (2) For the objective of minimizing maximum flow time on unrelated machines we give a simple \(2/\epsilon\)competitive algorithm when we augment the speed by \(\epsilon\). For \(m\) machines we show a lower bound of \(\Omega(m)\) on the competitive ratio if speed augmentation is not permitted. Our algorithm does not assign jobs to machines as soon as they arrive. To justify this "drawback" we show a lower bound of \(\Omega(\log m)\) on the competitive ratio of immediate dispatch algorithms. In both these lower bound constructions we use jobs whose processing times are in \(\{1,\infty\}\), and hence they apply to the more restrictive subset parallel setting. (3) For the objective of minimizing maximum weighted flow time on unrelated machines we establish a lower bound of \(\Omega(\log m)\)on the competitive ratio of any online algorithm which is permitted to use \(s = O(1)\) speed machines. In our lower bound construction, job j has a processing time of \(p_j\) on a subset of machines and infinity on others and has a weight \(1/p_j\). Hence this lower bound applies to the subset parallel setting for the special case of minimizing maximum stretch.

Angelini, Patrizio; Bläsius, Thomas; Rutter, Ignaz Testing Mutual Duality of Planar Graphs. International Symposium on Algorithms and Computation (ISAAC) 2013: 350360
We introduce and study the problem Mutual Planar Duality, which asks for planar graphs \(G_1\) and \(G_2\) whether \(G_1\) can be embedded such that its dual is isomorphic to \(G_2\). We show NPcompleteness for general graphs and give a lineartime algorithm for biconnected graphs. We consider the common dual relation ~, where \(G_1\) ~ \(G_2\) if and only they admit embeddings that result in the same dual graph. We show that ~ is an equivalence relation on the set of biconnected graphs and devise a succinct, SPQRtreelike representation of its equivalence classes. To solve Mutual Planar Duality for biconnected graphs, we show how to do isomorphism testing for two such representations in linear time. A special case of Mutual Planar Duality is testing whether a graph is selfdual. Our algorithm can handle the case of biconnected graphs in linear time and our NPhardness proof extends to selfduality and also to map selfduality testing (which additionally requires to preserve the embedding).

Bailly, Gilles; Oulasvirta, Antti; Kötzing, Timo; Hoppe, Sabrina MenuOptimizer: interactive optimization of menu systems. Symposium on User Interface Software and Technology (UIST) 2013: 331342
Menu systems are challenging to design because design spaces are immense, and several human factors affect user behavior. This paper contributes to the design of menus with the goal of interactively assisting designers with an optimizer in the loop. To reach this goal, 1) we extend a predictive model of user performance to account for expectations as to item groupings; 2) we adapt an ant colony optimizer that has been proven efficient for this class of problems; and 3) we present MenuOptimizer, a set of interactions integrated into a real interface design tool (QtDesigner). MenuOptimizer supports designers' abilities to cope with uncertainty and recognize good solutions. It allows designers to delegate combinatorial problems to the optimizer, which should solve them quickly enough without disrupting the design process. We show evidence that satisfactory menu designs can be produced for complex problems in minutes.

Benz, Florian; Kötzing, Timo An effective heuristic for the smallest grammar problem. Genetic and Evolutionary Computation Conference (GECCO) 2013: 487494
The smallest grammar problem is the problem of finding the smallest contextfree grammar that generates exactly one given sequence. Approximating the problem with a ratio of less than 8569/8568 is known to be NPhard. Most work on this problem has focused on finding decent solutions fast (mostly in linear time), rather than on good heuristic algorithms. Inspired by a new perspective on the problem presented by Carrascosa et al. (2010), we investigate the performance of different heuristics on the problem. The aim is to find a good solution on large instances by allowing more than linear time. We propose a hybrid of a maxmin ant system and a genetic algorithm that in combination with a novel local search outperforms the state of the art on all files of the Canterbury corpus, a standard benchmark suite. Furthermore, this hybrid performs well on a standard DNA corpus.

Biedl, Therese C.; Bläsius, Thomas; Niedermann, Benjamin; Nöllenburg, Martin; Prutkin, Roman; Rutter, Ignaz Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other GridBased Graph Drawings. Graph Drawing (GD) 2013: 460471
We present a simple and versatile formulation of gridbased graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a gridbased representation vertices and edges correspond to axisparallel boxes on an underlying integer grid; boxes can be further constrained in their shapes and interactions by additional problemspecific constraints. We describe a general \(d\)dimensional model for grid representation problems. This model can be used to solve a variety of NPhard graph problems, including pathwidth, bandwidth, optimum storientation, areaminimal (bark) visibility representation, boxicityk graphs and others. We implemented SATmodels for all of the above problems and evaluated them on the Rome graphs collection. The experiments show that our model successfully solves NPhard problems within few minutes on small to mediumsize Rome graphs.

Bläsius, Thomas; Karrer, Annette; Rutter, Ignaz Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices. Graph Drawing (GD) 2013: 220231
A simultaneous embedding (with fixed edges) of two graphs \(G^1\) and \(G^2\) with common graph \(G = G^1 \cap G^2\) is a pair of planar drawings of \(G^1\) and \(G^2\) that coincide on \(G\). It is an open question whether there is a polynomialtime algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three lineartime preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph \(G^\cup = G ^1 \cup G^2\) , (2) most separating pairs of \(G^{\cup}\), and (3) connected components of \(G\) that are biconnected but not a cycle. Second, we give an \(O(n^3)\)time algorithm solving Sefe for instances with the following restriction. Let \(u\) be a pole of a \(P\)node \(\mu\) in the SPQRtree of a block of \(G^1\) or \(G^2\) . Then at most three virtual edges of \(\mu\) may contain common edges incident to \(u\). All algorithms extend to the sunflower case, i.e., to the case of more than three graphs pairwise intersecting in the same common graph.

Bläsius, Thomas; Rutter, Ignaz Simultaneous PQOrdering with Applications to Constrained Embedding Problems. Symposium on Discrete Algorithms (SODA) 2013: 10301043
In this article, we define and study the new problem of SIMULTANEOUS PQORDERING. Its input consists of a set of PQtrees, which represent sets of circular orders of their leaves, together with a set of childparent relations between these PQtrees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every childparent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQORDERING is NPcomplete in general, and we identify a family of instances that can be solved efficiently, the 2fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQORDERING. In particular, we give lineartime algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a lineartime algorithm for PARTIALLY PQCONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQtrees that restrict the possible orderings of edges around vertices, and a quadratictime algorithm for SIMULTANEOUS EMBEDDING WITH FIXED EDGES for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.

Bläsius, Thomas; Rutter, Ignaz; Wagner, Dorothea Optimal Orthogonal Graph Drawing with Convex Bend Costs. International Colloquium on Automata, Languages, and Programming (ICALP) 2013: 184195
Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph \(G\) on \(n\) vertices with maximum degree 4 (4planar graph) and for each edge \(e\) a cost function \(cost_e \colon N_0 \rightarrow R\) defining costs depending on the number of bends \(e\) has, compute a planar orthogonal drawing of \(G\) of minimum cost. In this generality OptimalFlexDraw is NPhard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes time \(O(n, cdot, T_flow(n)\) and \(O(n^2, cdot, T_flow(n))\) for biconnected and connected graphs, respectively, where \(T_flow(n)\) denotes the time to compute a minimumcost flow in a planar network with multiple sources and sinks. Our result is the first polynomialtime bendoptimization algorithm for general 4planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.

Bringmann, Karl; Friedrich, Tobias Exact and Efficient Generation of Geometric Random Variates and Random Graphs. International Colloquium on Automata, Languages, and Programming (ICALP) 2013: 267278
The standard algorithm for fast generation of ErdHosRényi random graphs only works in the Real RAM model. The critical point is the generation of geometric random variates \(Geo(p)\), for which there is no algorithm that is both exact and efficient in any bounded precision machine model. For a RAM model with word size \(w=\Omega(\log\log(1/p))\), we show that this is possible and present an exact algorithm for sampling \(Geo(p)\) in optimal expected time \(O(1 + \log(1/p) / w)\). We also give an exact algorithm for sampling \(minn, Geo(p)\}\) in optimal expected time \(O(1 + \log(\min\{1/p,n\})/w)\). This yields a new exact algorithm for sampling ErdHosRényi and ChungLu random graphs of \(n\) vertices and \(m\) (expected) edges in optimal expected runtime \(O(n + m)\) on a RAM with word size \(w=\Theta(\log n)\).

Bringmann, Karl; Friedrich, Tobias Parameterized averagecase complexity of the hypervolume indicator. Genetic and Evolutionary Computation Conference (GECCO) 2013: 575582
Nominated for Best Paper Award (EMO Track)
The hypervolume indicator (HYP) is a popular measure for the quality of a set of \(n\) solutions in \(\mathbb{R}^d\). We discuss its asymptotic worstcase runtimes and several lower bounds depending on different complexitytheoretic assumptions. Assuming that P \(\neq\) NP, there is no algorithm with runtime \(poly(n,d)\). Assuming the exponential time hypothesis, there is no algorithm with runtime \(n^o(d)}\). In contrast to these worstcase lower bounds, we study the averagecase complexity of HYP for points distributed i.i.d. at random on a \(d\)dimensional simplex. We present a general framework which translates any algorithm for HYP with worstcase runtime \(n^f(d)}\) to an algorithm with worstcase runtime \(n^f(d) +1}\) and fixedparametertractable (FPT) averagecase runtime. This can be used to show that HYP can be solved in expected time \(O(d^d^2/2 n + d n^2)\), which implies that HYP is FPT on average while it is W1hard in the worstcase. For constant dimension \(d\) this gives an algorithm for HYP with runtime \(O(n^2)\) on average. This is the first result proving that HYP is asymptotically easier in the average case. It gives a theoretical explanation why most HYP algorithms perform much better on average than their theoretical worstcase runtime predicts.

Case, John; Kötzing, Timo Topological Separations in Inductive Inference. Algorithmic Learning Theory (ALT) 2013: 128142
Re learning in the limit from positive data, a major concern is which classes of languages are learnable with respect to a given learning criterion. We are particularly interested herein in the reasons for a class of languages to be unlearnable. We consider two types of reasons. One type is called topological where it does not help if the learners are allowed to be uncomputable (an example of Gold's is that no class containing an infinite language and all its finite sublanguages is learnable  even by an uncomputable learner). Another reason is called computational (where the learners are required to be algorithmic). In particular, two learning criteria might allow for learning different classes of languages from one another  but with dependence on whether the unlearnability is of type topological or computational. In this paper we formalize the idea of two learning criteria separating topologically in learning power. This allows us to study more closely why two learning criteria separate in learning power. For a variety of learning criteria, concerning vacillatory, monotone, (several kinds of) iterative and feedback learning, we show that certain learning criteria separate topologically, and certain others, which are known to separate, are shown not to separate topologically. Showing that learning criteria do not separate topologically implies that any known separation must necessarily exploit algorithmicity of the learner.

Croitoru, Cosmina; Kötzing, Timo A Normal Form for Argumentation Frameworks. Theorie and Applications of Formal Argumentation (TAFA) 2013: 3245
We study formal argumentation frameworks as introduced by Dung (1995). We show that any such argumentation framework can be syntactically augmented into a normal form (having a simplified attack relation), preserving the semantic properties of original arguments. An argumentation framework is in normal form if no argument attacks a conflicting pair of arguments. An augmentation of an argumentation framework is obtained by adding new arguments and changing the attack relation such that the acceptability status of original arguments is maintained in the new framework. Furthermore, we define joinnormal semantics leading to augmentations of the joined argumentation frameworks. Also, a rewriting technique which transforms in cubic time a given argumentation framework into a normal form is devised.

Feldmann, Matthias; Kötzing, Timo Optimizing expected path lengths with ant colony optimization using fitness proportional update. Foundations of Genetic Algorithms (FOGA) 2013: 6574
We study the behavior of a MaxMin Ant System (MMAS) on the stochastic singledestination shortest path (SDSP) problem. Two previous papers already analyzed this setting for two slightly different MMAS algorithms, where the pheromone update fitnessindependently rewards edges of the bestsofar solution. The first paper showed that, when the bestsofar solution is not reevaluated and the stochastic nature of the edge weights is due to noise, the MMAS will find a tree of edges successfully and efficiently identify a shortest path tree with minimal noisefree weights. The second paper used reevaluation of the bestsofar solution and showed that the MMAS finds paths which beat any other path in direct comparisons, if existent. For both results, for some random variables, this corresponds to a tree with minimal expected weights. In this work we analyze a variant of MMAS that works with fitnessproportional update on stochasticweight graphs with arbitrary random edge weights from \([0,1]\). For \(\delta\) such that any suboptimal path is worse by at least \(\delta\) than an optimal path, then, with suitable parameters, the graph will be optimized after \(O(n^3 ln n/\delta over \delta^3)\) iterations (in expectation). In order to prove the above result, the multiplicative and the variable drift theorem are adapted to continuous search spaces.

Freydenberger, Dominik D.; Kötzing, Timo Fast learning of restricted regular expressions and DTDs. International Conference on Database Theory (ICDT) 2013: 4556
We study the problem of generalizing from a finite sample to a language taken from a predefined language class. The two language classes we consider are subsets of the regular languages and have significance in the specification of XML documents (the classes corresponding to so called chain regular expressions, Chares, and to single occurrence regular expressions, Sores). The previous literature gave a number of algorithms for generalizing to Sores providing a trade off between quality of the solution and speed. Furthermore, a fast but nonoptimal algorithm for generalizing to Chares is known. For each of the two language classes we give an efficient algorithm returning a minimal generalization from the given finite sample to an element of the fixed language class; such generalizations are called descriptive. In this sense, both our algorithms are optimal.

Kawald, Bernd; Lenzner, Pascal On dynamics in selfish network creation. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2013: 8392
We consider the dynamic behavior of several variants of the Network Creation Game, introduced by Fabrikant et al. [PODC'03]. Equilibrium networks in these models have desirable properties like low social cost and small diameter, which makes them attractive for the decentralized creation of overlaynetworks. Unfortunately, due to the nonconstructiveness of the Nash equilibrium, no distributed algorithm for finding such networks is known. We treat these games as sequentialmove games and analyze if (uncoordinated) selfish play eventually converges to an equilibrium. Thus, we shed light on one of the most natural algorithms for this problem: distributed local search, where in each step some agent performs a myopic selfish improving move. We show that fast convergence is guaranteed for all versions of Swap Games, introduced by Alon et al. [SPAA'10], if the initial network is a tree. Furthermore, we prove that this process can be sped up to an almost optimal number of moves by employing a very natural move policy. Unfortunately, these positive results are no longer true if the initial network has cycles and we show the surprising result that even one nontree edge suffices to destroy the convergence guarantee. This answers an open problem from Ehsani et al. [SPAA'11] in the negative. Moreover, we show that on nontree networks no move policy can enforce convergence. We extend our negative results to the wellstudied original version, where agents are allowed to buy and delete edges as well. For this model we prove that there is no convergence guarantee  even if all agents play optimally. Even worse, if played on a noncomplete hostgraph, then there are instances where no sequence of improving moves leads to a stable network. Furthermore, we analyze whether costsharing has positive impact on the convergence behavior. For this we consider a version by Corbo and Parkes [PODC'05] where bilateral consent is needed for the creation of an edge and where edgecosts are shared among the involved agents. We show that employing such a costsharing rule yields even worse dynamic behavior..

Nallaperuma, Samadhi; Sutton, Andrew M.; Neumann, Frank Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problem. Congress on Evolutionary Computation (CEC) 2013: 20452052
We propose a new construction procedure for ant colony optimization (ACO) algorithms working on the Euclidean traveling salesperson problem (TSP) that preserves the ordering on the convex hull of the points in the instance. The procedure is inspired by theoretical analyses for simple evolutionary algorithms that are provably more efficient on instances where the number of inner points of the instance is not too large. We integrate the construction procedure into the wellknown MaxMin Ant System (MMAS) and empirically show that it leads to more efficient optimization on instances where the number of inner points is not too high.

Nallaperuma, Samadhi; Sutton, Andrew M.; Neumann, Frank Fixedparameter evolutionary algorithms for the Euclidean Traveling Salesperson problem. Congress on Evolutionary Computation (CEC) 2013: 20372044
We contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We exploit structural properties related to the optimization process of evolutionary algorithms for this problem and use them to bound the runtime of evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points \(k\) and shows that simple evolutionary algorithms solve the Euclidean TSP in expected time \(O(n^4k(2k  1)!)\). Moreover, we show that, under reasonable geometric constraints, a locally optimal 2opt tour can be found by randomized local search in expected time \(O(n^{2k}!)\).

Wagner, Markus; Friedrich, Tobias Efficient parent selection for ApproximationGuided Evolutionary multiobjective optimization. Congress on Evolutionary Computation (CEC) 2013: 18461853
The Pareto front of a multiobjective optimization problem is typically very large and can only be approximated. ApproximationGuided Evolution (AGE) is a recently presented evolutionary multiobjective optimization algorithm that aims at minimizing iteratively the approximation factor, which measures how well the current population approximates the Pareto front. It outperforms stateoftheart algorithms for problems with many objectives. However, AGE's performance is not competitive on problems with very few objectives. We study the reason for this behavior and observe that AGE selects parents uniformly at random, which has a detrimental effect on its performance. We then investigate different algorithmspecific selection strategies for AGE. The main difficulty here is finding a computationally efficient selection scheme which does not harm AGEs linear runtime in the number of objectives. We present several improved selections schemes that are computationally efficient and substantially improve AGE on lowdimensional objective spaces, but have no negative effect in highdimensional objective spaces.