2026

Döring, Michelle; Brill, Markus; Heitzig, Jobst The River Methodto appear at Proceedings of the 40th Annual AAAI Conference on Artificial Intelligence 2026
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We introduce River, a novel Condorcet-consistent voting method that is based on pairwise majority margins and can be seen as a simplified variation of Tideman's Ranked Pairs method. River is simple to explain, simple to compute even 'by hand', and gives rise to an easy-to-interpret certificate in the form of a directed tree. Like Ranked Pairs and Schulze's Beat Path method, River is a refinement of the Split Cycle method and shares with those many desirable properties, including independence of clones. Unlike the other three methods, River satisfies a strong form of resistance to agenda-manipulation that is known as independence of Pareto-dominated alternatives.
@inproceedings{döring_River_2025, abstract = {We introduce River, a novel Condorcet-consistent voting method that is based on pairwise majority margins and can be seen as a simplified variation of Tideman's Ranked Pairs method. River is simple to explain, simple to compute even 'by hand', and gives rise to an easy-to-interpret certificate in the form of a directed tree. Like Ranked Pairs and Schulze's Beat Path method, River is a refinement of the Split Cycle method and shares with those many desirable properties, including independence of clones. Unlike the other three methods, River satisfies a strong form of resistance to agenda-manipulation that is known as independence of Pareto-dominated alternatives.}, author = {Döring, Michelle and Brill, Markus and Heitzig, Jobst}, booktitle = {to appear at Proceedings of the 40th Annual AAAI Conference on Artificial Intelligence}, keywords = {aaai axiomaticanalysis jobstheitzig markusbrill michelledoering paretodomination river socialchoicefunction socialchoicetheory splitcycle votingmethod year2026}, title = {The River Method}, year = 2026 }

Döring, Michelle; Malanowski, Jannes; Neubert, Stefan Cost-Free Neutrality for the River Methodto appear at Proceedings of the 40th Annual AAAI Conference on Artificial Intelligence 2026
[ Abstract ] [ BibTeX ] [ Download ]
 
Recently, the River Method was introduced as novel refinement of the Split Cycle voting rule. The decision-making process of River is closely related to the well established Ranked Pairs Method. Both methods consider a margin graph computed from the voters' preferences and eliminate majority cycles in that graph to choose a winner. As ties can occur in the margin graph, a tiebreaker is required along with the preferences. While such a tiebreaker makes the computation efficient, it compromises the fundamental property of neutrality: the voting rule should not favor alternatives in advance. One way to reintroduce neutrality is to use Parallel-Universe Tiebreaking (PUT), where each alternative is a winner if it wins according to any possible tiebreaker. Unfortunately, computing the winners selected by Ranked Pairs with PUT is NP-complete. Given the similarity of River to Ranked Pairs, one might expect River to suffer from the same complexity. Surprisingly, we show the opposite: We present a polynomial-time algorithm for computing River winners with PUT, highlighting significant structural advantages of River over Ranked Pairs. Our Fused-Universe (FUN) algorithm simulates River for every possible tiebreaking in one pass. From the resulting FUN diagram one can then directly read off both the set of winners and, for each winner, a certificate that explains how this alternative dominates the others.
@inproceedings{doring2026costfree, abstract = {Recently, the River Method was introduced as novel refinement of the Split Cycle voting rule. The decision-making process of River is closely related to the well established Ranked Pairs Method. Both methods consider a margin graph computed from the voters' preferences and eliminate majority cycles in that graph to choose a winner. As ties can occur in the margin graph, a tiebreaker is required along with the preferences. While such a tiebreaker makes the computation efficient, it compromises the fundamental property of neutrality: the voting rule should not favor alternatives in advance. One way to reintroduce neutrality is to use Parallel-Universe Tiebreaking (PUT), where each alternative is a winner if it wins according to any possible tiebreaker. Unfortunately, computing the winners selected by Ranked Pairs with PUT is NP-complete. Given the similarity of River to Ranked Pairs, one might expect River to suffer from the same complexity. Surprisingly, we show the opposite: We present a polynomial-time algorithm for computing River winners with PUT, highlighting significant structural advantages of River over Ranked Pairs. Our Fused-Universe (FUN) algorithm simulates River for every possible tiebreaking in one pass. From the resulting FUN diagram one can then directly read off both the set of winners and, for each winner, a certificate that explains how this alternative dominates the others.}, author = {Döring, Michelle and Malanowski, Jannes and Neubert, Stefan}, booktitle = {to appear at Proceedings of the 40th Annual AAAI Conference on Artificial Intelligence}, keywords = {aaai bachelorthesis jannesmalanowski michelledoering river socialchoicefunction socialchoicetheory stefanneubert votingmethod year2026}, title = {Cost-Free Neutrality for the River Method}, year = 2026 }

Doerr, Benjamin; Krejca, Martin S.; Stanković, Milan Improved Runtime Guarantees for the SPEA2 Multi-Objective OptimizerAnnual AAAI Conference on Artificial Intelligence (AAAI) 2026: 36855–36863
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the NSGA-II, matching lower bounds exist. With a careful study of the more complex selection mechanism of the SPEA2, we show that it has very different population dynamics. From these, we prove runtime guarantees for the OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks that depend less on the population size. For example, we show that the SPEA2 with parent population size \(\mu \ge n - 2k + 3\) and offspring population size \(\lambda\) computes the Pareto front of the OneJumpZeroJump benchmark with gap size~\($k$\) in an expected number of \(O( (\lambda+\mu)n + n^{k+1})\) function evaluations. This shows that the best runtime guarantee of \(O(n^{k+1})\) is not only achieved for \(mu = \Theta(n)\) and \(lambda = O(n)\) but for arbitrary \(mu, lambda = O(n^k)\). Thus, choosing suitable parameters – a key challenge in using heuristic algorithms – is much easier for the SPEA2 than the NSGA-II.
@inproceedings{doerr2026improved, abstract = {Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the NSGA-II, matching lower bounds exist. With a careful study of the more complex selection mechanism of the SPEA2, we show that it has very different population dynamics. From these, we prove runtime guarantees for the OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks that depend less on the population size. For example, we show that the SPEA2 with parent population size \(\mu \ge n - 2k + 3\) and offspring population size \(\lambda\) computes the Pareto front of the OneJumpZeroJump benchmark with gap size $k$ in an expected number of \(O( (\lambda+\mu)n + n^{k+1})\) function evaluations. This shows that the best runtime guarantee of \(O(n^{k+1})\) is not only achieved for \(\mu = \Theta(n)\) and \(\lambda = O(n)\) but for arbitrary \(\mu, \lambda = O(n^k)\). Thus, choosing suitable parameters – a key challenge in using heuristic algorithms – is much easier for the SPEA2 than the NSGA-II.}, author = {Doerr, Benjamin and Krejca, Martin S. and Stanković, Milan}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {aaai benjamindoerr martinskrejca milanstankovic solelyextern year2026}, pages = {36855-36863}, title = {Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer}, year = 2026 }

2025

Berger, Julian; Friedrich, Tobias; Lenzner, Pascal; Paraskevi, Voula; Ruff, Janosch Strategic Network Creation for Enabling Greedy RoutingConference on Artificial Intelligence (AAAI) 2025
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Today we rely on networks that are created and maintained by smart devices. For such networks, there is no governing central authority but instead the network structure is shaped by the decisions of selfish intelligent agents. A key property of such communication networks is that they should be easy to navigate for routing data. For this, a common approach is greedy routing, where every device simply routes data to a neighbor that is closer to the respective destination. Networks of intelligent agents can be analyzed via a game-theoretic approach and in the last decades many variants of network creation games have been proposed and analyzed. In this paper we present the first game-theoretic network creation model that incorporates greedy routing, i.e., the strategic agents in our model are embedded in some metric space and strive for creating a network among themselves where all-pairs greedy routing is enabled. Besides this, the agents optimize their connection quality within the created network by aiming for greedy routing paths with low stretch. For our model, we analyze the existence of (approximate)-equilibria and the computational hardness in different underlying metric spaces. E.g., we characterize the set of equilibria in 1-2-metrics and tree metrics and show that Nash equilibria always exist. For Euclidean space, the setting which is most relevant in practice, we prove that equilibria are not guaranteed to exist but that the well-known \(\Theta\)-graph construction yields networks having a low stretch that are game-theoretically almost stable. For general metric spaces, we show that approximate equilibria exist where the approximation factor depends on the cost of maintaining any link.
@article{bflmr-aaai25, abstract = {Today we rely on networks that are created and maintained by smart devices. For such networks, there is no governing central authority but instead the network structure is shaped by the decisions of selfish intelligent agents. A key property of such communication networks is that they should be easy to navigate for routing data. For this, a common approach is greedy routing, where every device simply routes data to a neighbor that is closer to the respective destination. Networks of intelligent agents can be analyzed via a game-theoretic approach and in the last decades many variants of network creation games have been proposed and analyzed. In this paper we present the first game-theoretic network creation model that incorporates greedy routing, i.e., the strategic agents in our model are embedded in some metric space and strive for creating a network among themselves where all-pairs greedy routing is enabled. Besides this, the agents optimize their connection quality within the created network by aiming for greedy routing paths with low stretch. For our model, we analyze the existence of (approximate)-equilibria and the computational hardness in different underlying metric spaces. E.g., we characterize the set of equilibria in 1-2-metrics and tree metrics and show that Nash equilibria always exist. For Euclidean space, the setting which is most relevant in practice, we prove that equilibria are not guaranteed to exist but that the well-known \(\Theta\)-graph construction yields networks having a low stretch that are game-theoretically almost stable. For general metric spaces, we show that approximate equilibria exist where the approximation factor depends on the cost of maintaining any link.}, author = {Berger, Julian and Friedrich, Tobias and Lenzner, Pascal and Paraskevi, Voula and Ruff, Janosch}, journal = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai janoschruff julianberger paraskevimachaira pascallenzner tobiasfriedrich year2025}, title = {Strategic Network Creation for Enabling Greedy Routing}, year = 2025 }

Deligkas, Argyrios; Döring, Michelle; Eiben, Eduard; Goldsmith, Tiger-Lily; Skretas, George; Tennigkeit, Georg How Many Lines to Paint the City: Exact Edge-Cover in Temporal GraphsProceedings of the AAAI Conference on Artificial Intelligence 2025: 26498–26506
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.
@inproceedings{deligkas_HowMany_2025, abstract = {Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.}, author = {Deligkas, Argyrios and Döring, Michelle and Eiben, Eduard and Goldsmith, Tiger-Lily and Skretas, George and Tennigkeit, Georg}, journal = {Proceedings of the AAAI Conference on Artificial Intelligence}, keywords = {aaai argyriosdeligkas eduardeiben exactedge-cover georgeskretas georgtennigkeit michelledoering parameterizedcomplexity pathcover reachability temporalgraphs temporalpathgraph temporalpathumber tigerlilygoldsmith year2025}, month = {Apr.}, number = 25, pages = {26498-26506}, title = {How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs}, volume = 39, year = 2025 }

Doerr, Benjamin; Ivan, Tudor; Krejca, Martin S. Speeding Up the NSGA-II With a Simple Tie-Breaking RuleAnnual AAAI Conference on Artificial Intelligence (AAAI) 2025: 26964–26972
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The non-dominated sorting genetic algorithm II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II has difficulties with more than two objectives and that it is very sensitive to the choice of the population size. To overcome these difficulties, we analyze a simple tie-breaking rule in the selection of the next population. Similar rules have been proposed before, but have found only little acceptance. We prove the effectiveness of our tie-breaking rule via mathematical runtime analyses on the classic OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks. We prove that this modified NSGA-II can optimize the three benchmarks efficiently also for many objectives, in contrast to the exponential lower runtime bound previously shown for OneMinMax with three or more objectives. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum admissible size. For example, for the OneJumpZeroJump problem with representation length \($n$\) and gap parameter \($k$\), we show a runtime guarantee of \($O(\max\{n^{k+1},Nn\})$\) function evaluations when the population size is at least four times the size of the Pareto front. For population sizes larger than the minimal choice \($N = \Theta(n)$\), this result improves considerably over the \($\Theta(Nn^k)$\) runtime of the classic NSGA-II.
@inproceedings{doerr2025speeding, abstract = {The non-dominated sorting genetic algorithm II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II has difficulties with more than two objectives and that it is very sensitive to the choice of the population size. To overcome these difficulties, we analyze a simple tie-breaking rule in the selection of the next population. Similar rules have been proposed before, but have found only little acceptance. We prove the effectiveness of our tie-breaking rule via mathematical runtime analyses on the classic OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks. We prove that this modified NSGA-II can optimize the three benchmarks efficiently also for many objectives, in contrast to the exponential lower runtime bound previously shown for OneMinMax with three or more objectives. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum admissible size. For example, for the OneJumpZeroJump problem with representation length $n$ and gap parameter $k$, we show a runtime guarantee of $O(\max\{n^{k+1},Nn\})$ function evaluations when the population size is at least four times the size of the Pareto front. For population sizes larger than the minimal choice $N = \Theta(n)$, this result improves considerably over the $\Theta(Nn^k)$ runtime of the classic NSGA-II.}, author = {Doerr, Benjamin and Ivan, Tudor and Krejca, Martin S.}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {aaai benjamindoerr martinskrejca solelyextern tudorivan year2025}, pages = {26964-26972}, title = {Speeding Up the NSGA-II With a Simple Tie-Breaking Rule}, year = 2025 }

Doerr, Benjamin; Krejca, Martin S.; Rudolph, Günter Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer SpacesAnnual AAAI Conference on Artificial Intelligence (AAAI) 2025: 26955–26963
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables -- the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results -- however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.
@inproceedings{doerr2025runtime, abstract = {Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables – the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results – however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.}, author = {Doerr, Benjamin and Krejca, Martin S. and Rudolph, Günter}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {aaai benjamindoerr guenterrudolph martinskrejca solelyextern year2025}, pages = {26955-26963}, title = {Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces}, year = 2025 }

2024

Doerr, Benjamin; Echarghaoui, Aymen; Jamal, Mohammed; Krejca, Martin S. Runtime Analysis of the (µ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse PopulationsAnnual AAAI Conference on Artificial Intelligence (AAAI) 2024: 20683–20691
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Most evolutionary algorithms used in practice heavily employ crossover. In contrast, the rigorous understanding of how crossover is beneficial is largely lagging behind. In this work, we make a considerable step forward by analyzing the population dynamics of the \((\mu+1)\) genetic algorithm when optimizing the Jump benchmark. We observe (and prove via mathematical means) that once the population contains two different individuals on the local optimum, the diversity in the population increases in expectation. From this drift towards more diverse states, we show that a diversity suitable for crossover to be effective is reached quickly and, more importantly, then persists for a time that is at least exponential in the population size \(\mu\). This drastically improves over the previously best known guarantee, which is only quadratic in \(\mu\). Our new understanding of the population dynamics easily gives stronger performance guarantees. In particular, we derive that population sizes logarithmic in the problem size \(n\) already suffice to gain an \(\Omega(n)\)-factor runtime improvement from crossover (previous works achieved comparable bounds only with \(\mu=\Theta(n)\) or via a non-standard mutation rate).
@inproceedings{doerr2024runtime, abstract = {Most evolutionary algorithms used in practice heavily employ crossover. In contrast, the rigorous understanding of how crossover is beneficial is largely lagging behind. In this work, we make a considerable step forward by analyzing the population dynamics of the \((\mu+1)\) genetic algorithm when optimizing the Jump benchmark. We observe (and prove via mathematical means) that once the population contains two different individuals on the local optimum, the diversity in the population increases in expectation. From this drift towards more diverse states, we show that a diversity suitable for crossover to be effective is reached quickly and, more importantly, then persists for a time that is at least exponential in the population size \(\mu\). This drastically improves over the previously best known guarantee, which is only quadratic in \(\mu\). Our new understanding of the population dynamics easily gives stronger performance guarantees. In particular, we derive that population sizes logarithmic in the problem size \(n\) already suffice to gain an \(\Omega(n)\)-factor runtime improvement from crossover (previous works achieved comparable bounds only with \(\mu=\Theta(n)\) or via a non-standard mutation rate).}, author = {Doerr, Benjamin and Echarghaoui, Aymen and Jamal, Mohammed and Krejca, Martin S.}, booktitle = {Annual AAAI Conference on Artificial Intelligence (AAAI)}, keywords = {aaai aymenecharghaoui benjamindoerr jamalmohammed martinskrejca solelyextern year2024}, pages = {20683-20691}, title = {Runtime Analysis of the (µ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations}, year = 2024 }

Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network ModelsAnnual AAAI Conference on Artificial Intelligence 2024
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.
@inproceedings{friedrich2024irrelevance, abstract = {Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.}, author = {Friedrich, Tobias and Göbel, Andreas and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {Annual AAAI Conference on Artificial Intelligence}, keywords = {aaai andreasgoebel marcuspappik martinskrejca nicolasklodt tobiasfriedrich year2024}, title = {The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network Models}, year = 2024 }

2023

Blažej, Václav; Ganian, Robert; Knop, Dušan; Pokorný, Jan; Schierreich, Šimon; Simonov, Kirill The Parameterized Complexity of Network MicroaggregationConference on Artificial Intelligence (AAAI) 2023: 6262–6270
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameteri- zations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.
@inproceedings{blazej2023parameterized, abstract = {Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameteri- zations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.}, author = {Blažej, Václav and Ganian, Robert and Knop, Dušan and Pokorný, Jan and Schierreich, Šimon and Simonov, Kirill}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {sys:relevantfor:ae aaai kirillsimonov year2023}, pages = {6262–6270}, title = {The Parameterized Complexity of Network Microaggregation}, year = 2023 }

Brand, Cornelius; Ganian, Robert; Simonov, Kirill A Parameterized Theory of PAC LearningConference on Artificial Intelligence (AAAI) 2023: 6834–6841
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the class P in classical computational complexity. But while the nascent theory of parameterized complexity has allowed us to push beyond the P-NP “dichotomy” in classical computational complexity and identify the exact boundaries of tractability for numerous problems, there is no analogue in the domain of sample complexity that could push beyond efficient PAC learnability. As our core contribution, we fill this gap by developing a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity. Within the theory, we identify not one but two notions of fixed-parameter learnability that both form distinct counterparts to the class FPT—the core concept at the center of the parameterized complexity paradigm—and develop the machinery required to exclude fixed-parameter learnability. We then showcase the applications of this theory to identify refined boundaries of tractability for CNF and DNF learning as well as for a range of learning problems on graphs.
@inproceedings{brand2023parameterized, abstract = {Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the class P in classical computational complexity. But while the nascent theory of parameterized complexity has allowed us to push beyond the P-NP “dichotomy” in classical computational complexity and identify the exact boundaries of tractability for numerous problems, there is no analogue in the domain of sample complexity that could push beyond efficient PAC learnability. As our core contribution, we fill this gap by developing a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity. Within the theory, we identify not one but two notions of fixed-parameter learnability that both form distinct counterparts to the class FPT—the core concept at the center of the parameterized complexity paradigm—and develop the machinery required to exclude fixed-parameter learnability. We then showcase the applications of this theory to identify refined boundaries of tractability for CNF and DNF learning as well as for a range of learning problems on graphs.}, author = {Brand, Cornelius and Ganian, Robert and Simonov, Kirill}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {sys:relevantfor:ae aaai kirillsimonov year2023}, pages = {6834–6841}, title = {A Parameterized Theory of PAC Learning}, year = 2023 }

Krogmann, Simon; Lenzner, Pascal; Skopalik, Alexander Strategic Facility Location with Clients that Minimize Total Waiting TimeConference on Artificial Intelligence (AAAI) 2023: 5714–5721
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study a non-cooperative two-sided facility location game in which facilities and clients behave strategically. This is in contrast to many other facility location games in which clients simply visit their closest facility. Facility agents select a location on a graph to open a facility to attract as much purchasing power as possible, while client agents choose which facilities to patronize by strategically distributing their purchasing power in order to minimize their total waiting time. Here, the waiting time of a facility depends on its received total purchasing power. We show that our client stage is an atomic splittable congestion game, which implies existence, uniqueness and efficient computation of a client equilibrium. Therefore, facility agents can efficiently predict client behavior and make strategic decisions accordingly. Despite that, we prove that subgame perfect equilibria do not exist in all instances of this game and that their existence is NP-hard to decide. On the positive side, we provide a simple and efficient algorithm to compute 3-approximate subgame perfect equilibria.
@inproceedings{krogmann2023strategic, abstract = {We study a non-cooperative two-sided facility location game in which facilities and clients behave strategically. This is in contrast to many other facility location games in which clients simply visit their closest facility. Facility agents select a location on a graph to open a facility to attract as much purchasing power as possible, while client agents choose which facilities to patronize by strategically distributing their purchasing power in order to minimize their total waiting time. Here, the waiting time of a facility depends on its received total purchasing power. We show that our client stage is an atomic splittable congestion game, which implies existence, uniqueness and efficient computation of a client equilibrium. Therefore, facility agents can efficiently predict client behavior and make strategic decisions accordingly. Despite that, we prove that subgame perfect equilibria do not exist in all instances of this game and that their existence is NP-hard to decide. On the positive side, we provide a simple and efficient algorithm to compute 3-approximate subgame perfect equilibria.}, author = {Krogmann, Simon and Lenzner, Pascal and Skopalik, Alexander}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai pascallenzner simonkrogmann year2023}, number = 5, pages = {5714-5721}, title = {Strategic Facility Location with Clients that Minimize Total Waiting Time}, volume = 37, year = 2023 }

2022

Bandyapadhyay, Sayan; Fomin, Fedor V.; Golovach, Petr A.; Lochet, William; Purohit, Nidhi; Simonov, Kirill How to Find a Good Explanation for Clustering?Conference on Artificial Intelligence (AAAI) 2022: 3904–3912
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
\(k\)-means and \(k\)-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable \(k\)-means and \(k\)-median clustering in ICML 2020. In this model, a decision tree with \(k\) leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the ``best explanation'' by using a decision tree with \(k\) leaves? (2) For a given set of points, how to find a decision tree with \(k\) leaves minimizing the \(k\)-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.
@inproceedings{bandyapadhyay2022explanation, abstract = {\(k\)-means and \(k\)-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable \(k\)-means and \(k\)-median clustering in ICML 2020. In this model, a decision tree with \(k\) leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the ``best explanation'' by using a decision tree with \(k\) leaves? (2) For a given set of points, how to find a decision tree with \(k\) leaves minimizing the \(k\)-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.}, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Purohit, Nidhi and Simonov, Kirill}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {sys:relevantfor:ae aaai kirillsimonov year2022}, pages = {3904-3912}, title = {How to Find a Good Explanation for Clustering?}, year = 2022 }

2021

Aziz, Haris; Cseh, Agnes; Dickerson, John; McElfresh, Duncan Optimal Kidney Exchange with ImmunosuppressantsConference on Artificial Intelligence (AAAI) 2021: 21–29
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body's ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.
@inproceedings{haris2021optimal, abstract = {Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body's ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.}, author = {Aziz, Haris and Cseh, Agnes and Dickerson, John and McElfresh, Duncan}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai agnescseh duncanmcelfresh harisaziz johndickerson year2021}, pages = {21-29}, title = {Optimal Kidney Exchange with Immunosuppressants}, year = 2021 }

Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Lowski, Stefanie; Melnichenko, Anna Selfish Creation of Social NetworksConference on Artificial Intelligence (AAAI) 2021: 5185–5193
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Understanding real-world networks has been a core research endeavor throughout the last two decades. Network Creation Games are a promising approach for this from a game-theoretic perspective. In these games, selfish agents corresponding to nodes in a network strategically decide which links to form to optimize their centrality. Many versions have been introduced and analyzed, but none of them fits to modeling the evolution of social networks. In real-world social networks, connections are often established by recommendations from common acquaintances or by a chain of such recommendations. Thus establishing and maintaining a contact with a friend of a friend is easier than connecting to complete strangers. This explains the high clustering, i.e., the abundance of triangles, in real-world social networks. We propose and analyze a network creation model inspired by real-world social networks. Edges are formed in our model via bilateral consent of both endpoints and the cost for establishing and maintaining an edge is proportional to the distance of the endpoints before establishing the connection. We provide results for generic cost functions, which essentially only must be convex functions in the distance of the endpoints without the respective edge. For this broad class of cost functions, we provide many structural properties of equilibrium networks and prove (almost) tight bounds on the diameter, the Price of Anarchy and the Price of Stability. Moreover, as a proof-of-concept we show via experiments that the created equilibrium networks of our model indeed closely mimics real-world social networks. We observe degree distributions that seem to follow a power-law, high clustering, and low diameters. This can be seen as a promising first step towards game-theoretic network creation models that predict networks featuring all core real-world properties.
@inproceedings{bilo2021selfish, abstract = {Understanding real-world networks has been a core research endeavor throughout the last two decades. Network Creation Games are a promising approach for this from a game-theoretic perspective. In these games, selfish agents corresponding to nodes in a network strategically decide which links to form to optimize their centrality. Many versions have been introduced and analyzed, but none of them fits to modeling the evolution of social networks. In real-world social networks, connections are often established by recommendations from common acquaintances or by a chain of such recommendations. Thus establishing and maintaining a contact with a friend of a friend is easier than connecting to complete strangers. This explains the high clustering, i.e., the abundance of triangles, in real-world social networks. We propose and analyze a network creation model inspired by real-world social networks. Edges are formed in our model via bilateral consent of both endpoints and the cost for establishing and maintaining an edge is proportional to the distance of the endpoints before establishing the connection. We provide results for generic cost functions, which essentially only must be convex functions in the distance of the endpoints without the respective edge. For this broad class of cost functions, we provide many structural properties of equilibrium networks and prove (almost) tight bounds on the diameter, the Price of Anarchy and the Price of Stability. Moreover, as a proof-of-concept we show via experiments that the created equilibrium networks of our model indeed closely mimics real-world social networks. We observe degree distributions that seem to follow a power-law, high clustering, and low diameters. This can be seen as a promising first step towards game-theoretic network creation models that predict networks featuring all core real-world properties.}, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Lowski, Stefanie and Melnichenko, Anna}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai annamelnichenko davidebilo pascallenzner stefanielowski tobiasfriedrich year2021}, pages = {5185-5193}, title = {Selfish Creation of Social Networks}, year = 2021 }

2019

Friedrich, Tobias; Göbel, Andreas; Neumann, Frank; Quinzan, Francesco; Rothenberger, Ralf Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid ConstraintsConference on Artificial Intelligence (AAAI) 2019: 2272–2279
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone 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 non-monotone 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 real-world 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 well-suited 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.
@inproceedings{AAAI19a, abstract = {We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone 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 non-monotone 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 real-world 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 well-suited 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.}, author = {Friedrich, Tobias and Göbel, Andreas and Neumann, Frank and Quinzan, Francesco and Rothenberger, Ralf}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai andreasgoebel francescoquinzan frankneumann ralfrothenberger tobiasfriedrich year2019}, pages = {2272-2279}, title = {Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints}, year = 2019 }

Roostapour, Vahid; Neumann, Aneta; Neumann, Frank; Friedrich, Tobias Pareto Optimization for Subset Selection with Dynamic Cost ConstraintsConference on Artificial Intelligence (AAAI) 2019: 2354–2361
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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.
@inproceedings{AAAI19b, abstract = {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.}, author = {Roostapour, Vahid and Neumann, Aneta and Neumann, Frank and Friedrich, Tobias}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai anetaneumann frankneumann tobiasfriedrich vahidroostapour year2019}, pages = {2354-2361}, title = {Pareto Optimization for Subset Selection with Dynamic Cost Constraints}, year = 2019 }

2017

Friedrich, Tobias; Kötzing, Timo; Wagner, Markus A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local SearchConference on Artificial Intelligence (AAAI) 2017: 801–807
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
A common strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. However, while specific restart strategies have been developed for specific problems (and specific algorithms), restarts are typically not regarded as a general tool to speed up an optimization algorithm. In fact, many optimization algorithms do not employ restarts at all. Recently, "bet-and-run" was introduced in the context of mixed-integer programming, where first a number of short runs with randomized initial conditions is made, and then the most promising run of these is continued. In this article, we consider two classical NP-complete combinatorial optimization problems, traveling salesperson and minimum vertex cover, and study the effectiveness of different bet-and-run strategies. In particular, our restart strategies do not take any problem knowledge into account, nor are tailored to the optimization algorithm. Therefore, they can be used off-the-shelf. We observe that state-of-the-art solvers for these problems can benefit significantly from restarts on standard benchmark instances.
@inproceedings{DBLP:conf/aaai/0001K017, abstract = {A common strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. However, while specific restart strategies have been developed for specific problems (and specific algorithms), restarts are typically not regarded as a general tool to speed up an optimization algorithm. In fact, many optimization algorithms do not employ restarts at all. Recently, "bet-and-run" was introduced in the context of mixed-integer programming, where first a number of short runs with randomized initial conditions is made, and then the most promising run of these is continued. In this article, we consider two classical NP-complete combinatorial optimization problems, traveling salesperson and minimum vertex cover, and study the effectiveness of different bet-and-run strategies. In particular, our restart strategies do not take any problem knowledge into account, nor are tailored to the optimization algorithm. Therefore, they can be used off-the-shelf. We observe that state-of-the-art solvers for these problems can benefit significantly from restarts on standard benchmark instances.}, author = {Friedrich, Tobias and Kötzing, Timo and Wagner, Markus}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai markuswagner timokoetzing tobiasfriedrich year2017}, pages = {801-807}, title = {A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search}, year = 2017 }

Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sutton, Andrew M. Phase Transitions for Scale-Free SAT FormulasConference on Artificial Intelligence (AAAI) 2017: 3893–3899
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Recently, a number of non-uniform random satisfiability models have been proposed that are closer to practical satisfiability problems in some characteristics. In contrast to uniform random Boolean formulas, scale-free formulas have a variable occurrence distribution that follows a power law. It has been conjectured that such a distribution is a more accurate model for some industrial instances than the uniform random model. Though it seems that there is already an awareness of a threshold phenomenon in such models, there is still a complete picture lacking. In contrast to the uniform model, the critical density threshold does not lie at a single point, but instead exhibits a functional dependency on the power-law exponent. For scale-free formulas with clauses of length \(k = 2\), we give a lower bound on the phase transition threshold as a function of the scaling parameter. We also perform computational studies that suggest our bound is tight and investigate the critical density for formulas with higher clause lengths. Similar to the uniform model, on formulas with \(k \geq 3\), we find that the phase transition regime corresponds to a set of formulas that are difficult to solve by backtracking search.
@inproceedings{DBLP:conf/aaai/0001KRS17, abstract = {Recently, a number of non-uniform random satisfiability models have been proposed that are closer to practical satisfiability problems in some characteristics. In contrast to uniform random Boolean formulas, scale-free formulas have a variable occurrence distribution that follows a power law. It has been conjectured that such a distribution is a more accurate model for some industrial instances than the uniform random model. Though it seems that there is already an awareness of a threshold phenomenon in such models, there is still a complete picture lacking. In contrast to the uniform model, the critical density threshold does not lie at a single point, but instead exhibits a functional dependency on the power-law exponent. For scale-free formulas with clauses of length \(k = 2\), we give a lower bound on the phase transition threshold as a function of the scaling parameter. We also perform computational studies that suggest our bound is tight and investigate the critical density for formulas with higher clause lengths. Similar to the uniform model, on formulas with \(k \geq 3\), we find that the phase transition regime corresponds to a set of formulas that are difficult to solve by backtracking search.}, author = {Friedrich, Tobias and Krohmer, Anton and Rothenberger, Ralf and Sutton, Andrew M.}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai andrewmsutton antonkrohmer ralfrothenberger scalefree_sat tobiasfriedrich year2017}, pages = {3893-3899}, publisher = {AAAI Press}, title = {Phase Transitions for Scale-Free SAT Formulas}, year = 2017 }

Friedrich, Tobias; Neumann, Frank What’s Hot in Evolutionary ComputationConference on Artificial Intelligence (AAAI) 2017: 5064–5066
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We provide a brief overview on some hot topics in the area of evolutionary computation. Our main focus is on recent developments in the areas of combinatorial optimization and real-world applications. Furthermore, we highlight recent progress on the theoretical understanding of evolutionary computing methods.
@inproceedings{friedrich2017whats, abstract = {We provide a brief overview on some hot topics in the area of evolutionary computation. Our main focus is on recent developments in the areas of combinatorial optimization and real-world applications. Furthermore, we highlight recent progress on the theoretical understanding of evolutionary computing methods.}, author = {Friedrich, Tobias and Neumann, Frank}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai adelaide frankneumann tobiasfriedrich year2017}, pages = {5064-5066}, title = {What's Hot in Evolutionary Computation}, year = 2017 }

Katzmann, Maximilian; Komusiewicz, Christian Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover ProblemConference on Artificial Intelligence (AAAI) 2017: 846–852
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We investigate the potential of exhaustively exploring larger neighborhoods in local search algorithms for Minimum Vertex Cover. More precisely, we study whether, for moderate values of \(k\), it is feasible and worthwhile to determine, given a graph \(G\) with vertex cover \(C\), if there is a \(k\)-swap \(S\) such that \((C \setminus S) cup (S \setminus C)\) is a smaller vertex cover of \(G\). First, we describe an algorithm running in \(\Delta^{O(k) \cdot n\) time for searching the \(k\)-swap neighborhood on \(n\)-vertex graphs with maximum degree \(\Delta\). Then, we demonstrate that, by devising additional pruning rules that decrease the size of the search space, this algorithm can be implemented so that it solves the problem quickly for \(k \approx 20\). Finally, we show that it is worthwhile to consider moderately-sized \(k\)-swap neighborhoods. For our benchmark data set, we show that when combining our algorithm with a hill-climbing approach, the solution quality improves quickly with the radius \(k\) of the local search neighborhood and that in most cases optimal solutions can be found by setting \(k = 21\).
@inproceedings{DBLP:conf/aaai/KatzmannK17, abstract = {We investigate the potential of exhaustively exploring larger neighborhoods in local search algorithms for Minimum Vertex Cover. More precisely, we study whether, for moderate values of \(k\), it is feasible and worthwhile to determine, given a graph \(G\) with vertex cover \(C\), if there is a \(k\)-swap \(S\) such that \((C \setminus S) \cup (S \setminus C)\) is a smaller vertex cover of \(G\). First, we describe an algorithm running in \(\Delta^{O(k)} \cdot n\) time for searching the \(k\)-swap neighborhood on \(n\)-vertex graphs with maximum degree \(\Delta\). Then, we demonstrate that, by devising additional pruning rules that decrease the size of the search space, this algorithm can be implemented so that it solves the problem quickly for \(k \approx 20\). Finally, we show that it is worthwhile to consider moderately-sized \(k\)-swap neighborhoods. For our benchmark data set, we show that when combining our algorithm with a hill-climbing approach, the solution quality improves quickly with the radius \(k\) of the local search neighborhood and that in most cases optimal solutions can be found by setting \(k = 21\).}, author = {Katzmann, Maximilian and Komusiewicz, Christian}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {AAAI maximiliankatzmann year2017}, pages = {846-852}, title = {Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem}, year = 2017 }

2012

Sutton, Andrew M.; Neumann, Frank A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson ProblemConference on Artificial Intelligence (AAAI) 2012
[ Abstract ] [ BibTeX ] [ Download ]
 
Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, 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 investigate the structural properties in TSP instances that influence the optimization process of evolutionary algorithms and use this information to bound the runtime of simple evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points \(k\) and shows that \((\mu + \lambda)\) evolutionary algorithms solve the Euclidean TSP in expected time \(O((\mu / \lambda) cdot n^3 \gamma(\epsilon) + n \gamma(\epsilon)+(\mu / \lambda) cdot n^4k(2k-1)!)\) where \(\gamma\) is a function of the minimum angle \(epsilon\) between any three points. Finally, our analysis provides insights into designing a mutation operator that improves the upper bound on expected runtime. We show that a mixed mutation strategy that incorporates both 2-opt moves and permutation jumps results in an upper bound of \(O((\mu / \lambda) cdot n^3 \gamma(\epsilon) + n \gamma(\epsilon) + (\mu / \lambda) cdot n^2k(k-1)!)\) for the \((\mu + \lambda)\) EA.
@inproceedings{DBLP:conf/aaai/SuttonN12, abstract = {Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, 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 investigate the structural properties in TSP instances that influence the optimization process of evolutionary algorithms and use this information to bound the runtime of simple evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points \(k\) and shows that \((\mu + \lambda)\) evolutionary algorithms solve the Euclidean TSP in expected time \(O((\mu / \lambda) \cdot n^3 \gamma(\epsilon) + n \gamma(\epsilon)+(\mu / \lambda) \cdot n^{4k}(2k-1)!)\) where \(\gamma\) is a function of the minimum angle \(epsilon\) between any three points. Finally, our analysis provides insights into designing a mutation operator that improves the upper bound on expected runtime. We show that a mixed mutation strategy that incorporates both 2-opt moves and permutation jumps results in an upper bound of \(O((\mu / \lambda) \cdot n^3 \gamma(\epsilon) + n \gamma(\epsilon) + (\mu / \lambda) \cdot n^{2k}(k-1)!)\) for the \((\mu + \lambda)\) EA.}, author = {Sutton, Andrew M. and Neumann, Frank}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai andrewmsutton frankneumann imported year2012}, publisher = {{AAAI} Press}, title = {A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem}, year = 2012 }