Clean Citation Style 002
{ "authors" : [{ "lastname":"Bläsius" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/thomasblaesius.html" , "mail":"thomas.blasius(at)hpi.de" }, { "lastname":"Casel" , "initial":"K" , "url":"https://hpi.de/friedrich/publications/people/katrincasel.html" , "mail":"katrin.casel(at)hpi.de" }, { "lastname":"Chauhan" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/ankitchauhan.html" , "mail":"ankit.chauhan(at)hpi.de" }, { "lastname":"Doskoč" , "initial":"V" , "url":"https://hpi.de/friedrich/publications/people/vanjadoskoc.html" , "mail":"vanja.doskoc(at)hpi.de" }, { "lastname":"Elijazyfer" , "initial":"Z" , "url":"https://hpi.de/friedrich/people/zienaelijazyfer.html" , "mail":"ziena.elijazyfer(at)hpi.de" }, { "lastname":"Fischbeck" , "initial":"P" , "url":"https://hpi.de/friedrich/publications/people/philippfischbeck.html" , "mail":"philipp.fischbeck(at)hpi.de" }, { "lastname":"Friedrich" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/tobiasfriedrich.html" , "mail":"friedrich(at)hpi.de" }, { "lastname":"Göbel" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/andreasgoebel.html" , "mail":"andreas.goebel(at)hpi.de" }, { "lastname":"Katzmann" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/maximiliankatzmann.html" , "mail":"maximilian.katzmann(at)hpi.de" }, { "lastname":"Kötzing" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/timokoetzing.html" , "mail":"timo.koetzing(at)hpi.de" }, { "lastname":"Krejca" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/martinkrejca.html" , "mail":"martin.krejca(at)hpi.de" }, { "lastname":"Krohmer" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/antonkrohmer.html" , "mail":"none" }, { "lastname":"Lagodzinski" , "initial":"G" , "url":"https://hpi.de/friedrich/publications/people/gregorlagodzinski.html" , "mail":"gregor.lagodzinski(at)hpi.de" }, { "lastname":"Lenzner" , "initial":"P" , "url":"https://hpi.de/friedrich/publications/people/pascallenzner.html" , "mail":"pascal.lenzner(at)hpi.de" }, { "lastname":"Melnichenko" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/annamelnichenko.html" , "mail":"anna.melnichenko(at)hpi.de" }, { "lastname":"Molitor" , "initial":"L" , "url":"https://hpi.de/friedrich/publications/people/louisemolitor.html" , "mail":"louise.molitor(at)hpi.de" }, { "lastname":"Neubert" , "initial":"S" , "url":"https://hpi.de/friedrich/publications/people/stefanneubert.html" , "mail":"stefan.neubert(at)hpi.de" }, { "lastname":"Quinzan" , "initial":"F" , "url":"https://hpi.de/friedrich/publications/people/francescoquinzan.html" , "mail":"francesco.quinzan(at)hpi.de" }, { "lastname":"Rizzo" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/manuelrizzo.html" , "mail":"manuel.rizzo(at)hpi.de" }, { "lastname":"Rothenberger" , "initial":"R" , "url":"https://hpi.de/friedrich/publications/people/ralfrothenberger.html" , "mail":"ralf.rothenberger(at)hpi.de" }, { "lastname":"Schirneck" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/martinschirneck.html" , "mail":"martin.schirneck(at)hpi.de" }, { "lastname":"Seidel" , "initial":"K" , "url":"https://hpi.de/friedrich/publications/people/karenseidel.html" , "mail":"karen.seidel(at)hpi.de" }, { "lastname":"Sutton" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/andrewmsutton.html" , "mail":"none" }, { "lastname":"Weyand" , "initial":"C" , "url":"https://hpi.de/friedrich/publications/people/christopherweyand.html" , "mail":"none" }]}

Friedrich, Tobias; Göbel, Andreas; Neumann, Frank; Quinzan, Francesco; Rothenberger, Ralf Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints. Conference on Artificial Intelligence (AAAI) 2019: 22722279
We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider nonmonotone submodular functions and monotone subadditive functions. Even though constrained maximization problems of monotone submodular functions have been extensively studied, little is known about greedy maximization of nonmonotone submodular functions or monotone subadditive functions. We give approximation guarantees for GREEDY on these problems, in terms of the curvature. We find that this simple heuristic yields a strong approximation guarantee on a broad class of functions. We discuss the applicability of our results to three realworld problems: Maximizing the determinant function of a positive semidefinite matrix, and related problems such as the maximum entropy sampling problem, the constrained maximum cut problem on directed graphs, and combinatorial auction games. We conclude that GREEDY is wellsuited to approach these problems. Overall, we present evidence to support the idea that, when dealing with constrained maximization problems with bounded curvature, one needs not search for (approximate) monotonicity to get good approximate solutions.

Roostapour, Vahid; Neumann, Aneta; Neumann, Frank; Friedrich, Tobias Pareto Optimization for Subset Selection with Dynamic Cost Constraints. Conference on Artificial Intelligence (AAAI) 2019: 23542361
In this paper, we consider subset selection problems for functions \(f\) with constraints where the constraint bound \(B\) changes over time. We point out that adaptive variants of greedy approaches commonly used in the area of submodular optimization are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a \( phi= (\alpha_f/2)(1\frac{1}{e^{\alpha_f}})\)approximation, where \(\alpha_f\) is the submodularity ratio, for each possible constraint bound \(b \leq B\). Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that \(B\) increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms.

Feldotto, Matthias; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander From Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation. Autonomous Agents and Multiagent Systems (AAMAS) 2019: 19491951
Competing firms tend to select similar locations for their stores. This phenomenon, called the principle of minimum differentiation, was captured by Hotelling with a landmark model of spatial competition but is still the object of an ongoing scientific debate. Although consistently observed in practice, many more realistic variants of Hotelling's model fail to support minimum differentiation or do not have pure equilibria at all. In particular, it was recently proven for a generalized model which incorporates negative network externalities and which contains Hotelling's model and classical selfish load balancing as special cases, that the unique equilibria do not adhere to minimum differentiation. Furthermore, it was shown that for a significant parameter range pure equilibria do not exist. We derive a sharp contrast to these previous results by investigating Hotelling's model with negative network externalities from an entirely new angle: approximate pure subgame perfect equilibria. This approach allows us to prove analytically and via agentbased simulations that approximate equilibria having good approximation guarantees and that adhere to minimum differentiation exist for the full parameter range of the model. Moreover, we show that the obtained approximate equilibria have high social welfare.

Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling. Algorithm Engineering and Experiments (ALENEX) 2019: 130143
We devise an enumeration method for inclusionwise minimal hitting sets in hypergraphs. It has delay \(O(m^{k^\ast+1} \cdot n^2)\) and uses linear space. Hereby, \(n\) is the number of vertices, \(m\) the number of hyperedges, and \(k^\ast\) the rank of the transversal hypergraph. In particular, on classes of hypergraphs for which the cardinality \(k^\ast\) of the largest minimal hitting set is bounded, the delay is polynomial. The algorithm solves the extension problem for minimal hitting sets as a subroutine. We show that the extension problem is W[3]complete when parameterised by the cardinality of the set which is to be extended. For the subroutine, we give an algorithm that is optimal under the exponential time hypothesis. Despite these lower bounds, we provide empirical evidence showing that the enumeration outperforms the theoretical worstcase guarantee on hypergraphs arising in the profiling of relational databases, namely, in the detection of unique column combinations.

Fokina, Ekaterina; Kötzing, Timo; San Mauro, Luca Limit Learning Equivalence Structures. Algorithmic Learning Theory (ALT) 2019: 120
While most research in Goldstyle learning focuses on learning formal languages, we consider the identification of computable structures, specifically equivalence structures. In our core model the learner gets more and more information about which pairs of elements of a structure are related and which are not. The aim of the learner is to find (an effective description of) the isomorphism type of the structure presented in the limit. In accordance with language learning we call this learning criterion InfExlearning (explanatory learning from informant). We start with a discussion and separations of different variants of this learning criterion, including learning from text (where the only information provided is which elements are related, and not which elements are not related) and finite learning (where the first actual conjecture of the learner has to be correct). This gives first intuitions and examples for what (classes of) structures are learnable and which are not. Our main contribution is a complete characterization of the learnable classes of structures in terms of a combinatorial property of the classes. This property allows us to derive a bound of \(\mathbf{0''}\) on the computational complexity required to learn uniformly enumerable classes of structures. Finally, we show how learning classes of structures relates to learning classes of languages by mapping learning tasks for structures to equivalent learning tasks for languages.

Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian Extension of vertex cover and independent set in some classes of graphs and generalizations. International Conference on Algorithms and Complexity (CIAC) 2019: 124136
We study extension variants of the classical problems Vertex Cover and Independent Set. Given a graph \(G = (V, E)\) and a vertex set \(U \subseteq V\), it is asked if there exists a minimal vertex cover (resp. maximal independent set) \(S\) with \(U \subseteq S\) (resp. \(U \supseteq S\)). Possibly contradicting intuition, these problems tend to be NPcomplete, even in graph classes where the classical problem can be solved efficiently. Yet, we exhibit some graph classes where the extension variant remains polynomialtime solvable. We also study the parameterized complexity of theses problems, with parameter \(U\), as well as the optimality of simple exact algorithms under ETH. All these complexity considerations are also carried out in very restricted scenarios, be it degree or topological restrictions (bipartite, planar or chordal graphs). This also motivates presenting some explicit branching algorithms for degreebounded instances. We further discuss the price of extension, measuring the distance of \(U\) to the closest set that can be extended, which results in natural optimization problems related to extension problems for which we discuss polynomialtime approximability.

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, Christopher Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs. European Symposium on Algorithms (ESA) 2019: 21:221:14
EATCS Best Paper Award
Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a powerlaw degree distribution with controllable exponent \(\beta\), and high clustering that can be controlled via the temperature \(T\). We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support nonzero temperatures. Though nonzero temperatures are crucial for many applications, most existing generators are restricted to \(T = 0\). We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the nontrivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify \(\bar{d}\) as input and obtain a graph with expected average degree \(\bar{d}\). Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straightforward inclusion does not hold in practice. However, the difference is negligible for most use cases.

Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian Extension of some edge graph problems: standard and parameterized complexity. Fundamentals of Computation Theory (FCT) 2019: 185200
We consider extension variants of some edge optimization problems in graphs containing the classical Edge Cover, Matching, and Edge Dominating Set problems. Given a graph \(G=(V,E)\) and an edge set \(U \subseteq E\), it is asked whether there exists an inclusionwise minimal (resp., maximal) feasible solution \(E'\) which satisfies a given property, for instance, being an edge dominating set (resp., a matching) and containing the forced edge set \(U\) (resp., avoiding any edges from the forbidden edge set \(E U\)). We present hardness results for these problems, for restricted instances such as bipartite or planar graphs. We counterbalance these negative results with parameterized complexity results. We also consider the price of extension, a natural optimization problem variant of extension problems, leading to some approximation results.

Doerr, Benjamin; Kötzing, Timo Multiplicative UpDrift. Genetic and Evolutionary Computation Conference (GECCO) 2019
Drift analysis aims at translating the expected progress of an evo lutionary algorithm (or more generally, a random process) into a probabilistic guarantee on its run time (hitting time). So far, drift arguments have been successfully employed in the rigorous analy sis of evolutionary algorithms, however, only for the situation that the progress is constant or becomes weaker when approaching the target. Motivated by questions like how fast fit individuals take over a population, we analyze random processes exhibiting a multiplica tive growth in expectation. We prove a drift theorem translating this expected progress into a hitting time. This drift theorem gives a sim ple and insightful proof of the levelbased theorem first proposed by Lehre (2011). Our version of this theorem has, for the first time, the bestpossible linear dependence on the growth parameter \(\delta\) (the previousbest was quadratic). This gives immediately stronger run time guarantees for a number of applications.

Friedrich, Tobias; Rothenberger, Ralf The Satisfiability Threshold for NonUniform Random 2SAT. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 61:161:14
Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. Its worstcase hardness lies at the core of computational complexity theory, for example in the form of NPhardness and the (Strong) Exponential Time Hypothesis. In practice however, SAT instances can often be solved efficiently. This contradicting behavior has spawned interest in the averagecase analysis of SAT and has triggered the development of sophisticated rigorous and nonrigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, most theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, realworld instances often exhibit large fluctuations in variable occurrence. This can be modeled by a nonuniform distribution of the variables, which can result in distributions closer to industrial SAT instances. We study satisfiability thresholds of nonuniform random 2SAT with n variables and m clauses and with an arbitrary probability distribution \((p_i)_{i \in [n]}\) with \(p_1 \geq p_2 \geq \dots \geq p_n > 0\) over the n variables. We show for \(p_1^2 = \Theta(\sum_{i=1}^n p_i^2)\) that the asymptotic satisfiability threshold is at \(m = \Theta((1− \sum_{i=1}^n p_i^2) / (p_1 cdot (\sum_{i=2}^n p_i^2)^{1/2}))\) and that it is coarse. For \(p_1^2 = o( \sum_{i=1}^n p_i^2)\) we show that there is a sharp satisfiability threshold at \(m = (\sum_{i=1}^n p_i^2)^{−1}\). This result generalizes the seminal works by Chvatal and Reed [FOCS 1992] and by Goerdt [JCSS 1996].

Casel, Katrin; Day, Joel D.; Fleischmann, Pamela; Kociumaka, Tomasz; Manea, Florin; Schmid, Markus L. Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 109:1109:16
We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graphparameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NPhard but fixed parameter tractable (when the locality number or the alphabet size is treated as a parameter), and can be approximated with ratio \(O(\sqrt{\log opt} \log n)\). As a byproduct, we also relate cutwidth via the locality number to pathwidth, which is of independent interest, since it improves the currently best known approximation algorithm for cutwidth. In addition to these main results, we also consider the possibility of greedybased approximation algorithms for the locality number.

Peters, Jannik; Stephan, Daniel; Amon, Isabel; Gawendowicz, Hans; Lischeid, Julius; Salabarria, Julius; Umland, Jonas; Werner, Felix; Krejca, Martin S.; Rothenberger, Ralf; Kötzing, Timo; Friedrich, Tobias Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard RealWorld Staff Assignment Problem. International Conference on Automated Planning and Scheduling (ICAPS) 2019: 541554
Assigning staff to engagements according to hard constraints while optimizing several objectives is a task encountered by many companies on a regular basis. Simplified versions of such assignment problems are NPhard. Despite this, a typical approach to solving them consists of formulating them as mixed integer programming (MIP) problems and using a stateoftheart solver to get solutions that closely approximate the optimum. In this paper, we consider a complex realworld staff assignment problem encountered by the professional service company KPMG, with the goal of finding an algorithm that solves it faster and with a better solution than a commercial MIP solver. We follow the evolutionary algorithm (EA) metaheuristic and design a search heuristic which iteratively improves a solution using domainspecific mutation operators. Furthermore, we use a flow algorithm to optimally solve a subproblem, which tremendously reduces the search space for the EA. For our realworld instance of the assignment problem, given the same total time budget of \(100\) hours, a parallel EA approach finds a solution that is only \(1.7\)% away from an upper bound for the (unknown) optimum within under five hours, while the MIP solver Gurobi still has a gap of \(10.5\) %.

Friedrich, Tobias; Rothenberger, Ralf Sharpness of the Satisfiability Threshold for NonUniform Random kSAT. International Joint Conference on Artificial Intelligence (IJCAI) 2019: 61516155
Extended abstract
We study nonuniform random kSAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number \(t = t(n)\) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random kSAT with an ensemble \((p_n)_{n\in\mathbb{N}}\) of arbitrary probability distributions on the variable occurrences is sharp if \(\p\_2^2 = O_n(t^{2/k})\) and \(\p\_infty = o_n(t^{k/(2k1)} \log^{(k1)/(2k1)}(t))\). This result generalizes Friedgut’s sharpness result from uniform to nonuniform random kSAT and implies sharpness for thresholds of a wide range of random kSAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a powerlaw distribution.

Gao, Ziyuan; Jain, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Melnikov, Alexander; Seidel, Karen; Stephan, Frank Random Subgroups of Rationals. International Symposium on Mathematical Foundations of Computer Science (MFCS) 2019: 25:125:14
This paper introduces and studies a notion of algorithmic randomness for subgroups of rationals. Given a randomly generated additive subgroup \((G,+)\) of rationals, two main questions are addressed: first, what are the modeltheoretic and recursiontheoretic properties of \((G,+)\); second, what learnability properties can one extract from \(G\) and its subclass of finitely generated subgroups? For the first question, it is shown that the theory of \((G,+)\) coincides with that of the additive group of integers and is therefore decidable; furthermore, while the word problem for \(G\) with respect to any generating sequence for \(G\) is not even semidecidable, one can build a generating sequence \(\beta\) such that the word problem for \(G\) with respect to \(\beta\) is corecursively enumerable (assuming that the set of generators of \(G\) is limitrecursive). In regard to the second question, it is proven that there is a generating sequence \(\beta\) for \(G\) such that every nontrivial finitely generated subgroup of \(G\) is recursively enumerable and the class of all such subgroups of \(G\) is behaviourally correctly learnable, that is, every nontrivial finitely generated subgroup can be semantically identified in the limit (again assuming that the set of generators of \(G\) is limitrecursive). On the other hand, the class of nontrivial finitely generated subgroups of \(G\) cannot be syntactically identified in the limit with respect to any generating sequence for \(G\). The present work thus contributes to a recent line of research studying algorithmically random infinite structures and uncovers an interesting connection between the arithmetical complexity of the set of generators of a randomly generated subgroup of rationals and the learnability of its finitely generated subgroups.

Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna Geometric Network Creation Games. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323332
Network Creation Games are a wellknown approach for explaining and analyzing the structure, quality and dynamics of realworld networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unitweight edges. In practice, e.g. when constructing a fiberoptic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edgeweighted graphs. We incorporate arbitrary edge weights by generalizing the wellknown model by Fabrikant et al.~[PODC'03] to edgeweighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the stateoftheart for the unitweight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight nonconstant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the nonmetric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the gametheoretic analogue of a variant of the classical Network Design Problem. Thus, lowcost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.

Friedrich, Tobias From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity. Symposium Theoretical Aspects of Computer Science (STACS) 2019: 5:1–5:9
Network science is driven by the question which properties large realworld networks have and how we can exploit them algorithmically. In the past few years, hyperbolic graphs have emerged as a very promising model for scalefree networks. The connection between hyperbolic geometry and complex networks gives insights in both directions: (1) Hyperbolic geometry forms the basis of a natural and explanatory model for realworld networks. Hyperbolic random graphs are obtained by choosing random points in the hyperbolic plane and connecting pairs of points that are geometrically close. The resulting networks share many structural properties for example with online social networks like Facebook or Twitter. They are thus well suited for algorithmic analyses in a more realistic setting. (2) Starting with a realworld network, hyperbolic geometry is wellsuited for metric embeddings. The vertices of a network can be mapped to points in this geometry, such that geometric distances are similar to graph distances. Such embeddings have a variety of algorithmic applications ranging from approximations based on efficient geometric algorithms to greedy routing solely using hyperbolic coordinates for navigation decisions.

Bläsius, Thomas; Friedrich, Tobias; Sutton, Andrew M. On the Empirical Time Complexity of ScaleFree 3SAT at the Phase Transition. Tools and Algorithms for the Construction and Analysis of Systems (TACAS) 2019: 117134
The hardness of formulas at the solubility phase transition of random propositional satisfiability (SAT) has been intensely studied for decades both empirically and theoretically. Solvers based on stochastic local search (SLS) appear to scale very well at the critical threshold, while complete backtracking solvers exhibit exponential scaling. On industrial SAT instances, this phenomenon is inverted: backtracking solvers can tackle large industrial problems, where SLSbased solvers appear to stall. Industrial instances exhibit sharply different structure than uniform random instances. Among many other properties, they are often heterogeneous in the sense that some variables appear in many while others appear in only few clauses. We conjecture that the heterogeneity of SAT formulas alone already contributes to the tradeoff in performance between SLS solvers and complete backtracking solvers. We empirically determine how the run time of SLS vs. backtracking solvers depends on the heterogeneity of the input, which is controlled by drawing variables according to a scalefree distribution. Our experiments reveal that the efficiency of complete solvers at the phase transition is strongly related to the heterogeneity of the degree distribution. We report results that suggest the depth of satisfying assignments in complete search trees is influenced by the level of heterogeneity as measured by a powerlaw exponent. We also find that incomplete SLS solvers, which scale well on uniform instances, are not affected by heterogeneity. The main contribution of this paper utilizes the scalefree random 3SAT model to isolate heterogeneity as an important factor in the scaling discrepancy between complete and SLS solvers at the uniform phase transition found in previous works.

Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, Martin Understanding the Effectiveness of Data Reduction in Public Transportation Networks. Workshop on Algorithms and Models for the Web Graph (WAW) 2019: 87101
Given a public transportation network of stations and connections, we want to find a minimum subset of stations such that each connection runs through a selected station. Although this problem is NPhard in general, realworld instances are regularly solved almost completely by a set of simple reduction rules. To explain this behavior, we view transportation networks as hitting set instances and identify two characteristic properties, locality and heterogeneity. We then devise a randomized model to generate hitting set instances with adjustable properties. While the heterogeneity does influence the effectiveness of the reduction rules, the generated instances show that locality is the significant factor. Beyond that, we prove that the effectiveness of the reduction rules is independent of the underlying graph structure. Finally, we show that high locality is also prevalent in instances from other domains, facilitating a fast computation of minimum hitting sets.

Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, David Convergence and Hardness of Strategic Schelling Segregation. Web and Internet Economics (WINE) 2019
The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least \($\tau$\), for some \($0<\tau<1$\). Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized gametheoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible nonconvergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in \($\mathcal{O}(m)$\) steps, where \($m$\) is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.