2021

• 
  Aziz, Haris; Cseh, Agnes; Dickerson, John; McElfresh, DuncanOptimal Kidney Exchange with Immunosuppressants. Conference on Artificial Intelligence (AAAI) 2021
  [ BibTeX ]
   
  @inproceedings{haris2021optimal, 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}, title = {Optimal Kidney Exchange with Immunosuppressants}, year = 2021 }
• 
  Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Lowski, Stefanie; Melnichenko, AnnaSelfish Creation of Social Networks. Conference on Artificial Intelligence (AAAI) 2021
  [ Abstract ] [ BibTeX ] [ 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}, title = {Selfish Creation of Social Networks}, year = 2021 }
• 
  Kraiczy, Sonja; Cseh, Ágnes; Manlove, DavidOn Weakly and Strongly Popular Rankings. Autonomous Agents and Multiagent Systems (AAMAS) 2021
  [ BibTeX ]
   
  @inproceedings{kraiczy2021weakly, author = {Kraiczy, Sonja and Cseh, Ágnes and Manlove, David}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas agnescseh davidfmanlove sonjakraiczy year2021}, title = {On Weakly and Strongly Popular Rankings}, year = 2021 }
• 
  Aziz, Haris; Chan, Hau; Cseh, Ágnes; Li, Bo; Ramezani, Fahimeh; Wang, ChenhaoMulti-Robot Task Allocation—Complexity and Approximation. Autonomous Agents and Multiagent Systems (AAMAS) 2021
  [ BibTeX ]
   
  @inproceedings{aziz2021multirobot, author = {Aziz, Haris and Chan, Hau and Cseh, Ágnes and Li, Bo and Ramezani, Fahimeh and Wang, Chenhao}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas agnescseh boli chenhaowang fahimehramezani harisaziz hauchan year2021}, title = {Multi-Robot Task Allocation—Complexity and Approximation}, year = 2021 }
• 
  Quinzan, Francesco; Doskoč, Vanja; Göbel, Andreas; Friedrich, TobiasAdaptive Sampling for Fast Constrained Maximization of Submodular Functions. Artificial Intelligence and Statistics (AISTATS) 2021: 964-972
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  Several large-scale machine learning tasks, such as data summarization, can be approached by maximizing functions that satisfy submodularity. These optimization problems often involve complex side constraints, imposed by the underlying application. In this paper, we develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular maximization under general side constraints. The adaptive complexity of a problem is the minimal number of sequential rounds required to achieve the objective. Our algorithm is suitable to maximize a non-monotone submodular function under a \(p\)-system side constraint, and it achieves a \((p + O({\sqrt{p}}))\)-approximation for this problem, after only poly-logarithmic adaptive rounds and polynomial queries to the valuation oracle function. Furthermore, our algorithm achieves a \(p + O(1))\)-approximation when the given side constraint is a \(p\)-extendible system. This algorithm yields an exponential speed-up, with respect to the adaptivity, over any other known constant-factor approximation algorithm for this problem. It also competes with previous known results in terms of the query complexity. We perform various experiments on various real-world applications. We find that, in comparison with commonly used heuristics, our algorithm performs better on these instances.
  @inproceedings{doskoc2021adaptive, abstract = {Several large-scale machine learning tasks, such as data summarization, can be approached by maximizing functions that satisfy submodularity. These optimization problems often involve complex side constraints, imposed by the underlying application. In this paper, we develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular maximization under general side constraints. The adaptive complexity of a problem is the minimal number of sequential rounds required to achieve the objective. Our algorithm is suitable to maximize a non-monotone submodular function under a \(p\)-system side constraint, and it achieves a \((p + O({\sqrt{p}}))\)-approximation for this problem, after only poly-logarithmic adaptive rounds and polynomial queries to the valuation oracle function. Furthermore, our algorithm achieves a \(p + O(1))\)-approximation when the given side constraint is a \(p\)-extendible system. This algorithm yields an exponential speed-up, with respect to the adaptivity, over any other known constant-factor approximation algorithm for this problem. It also competes with previous known results in terms of the query complexity. We perform various experiments on various real-world applications. We find that, in comparison with commonly used heuristics, our algorithm performs better on these instances.}, author = {Quinzan, Francesco and Doskoč, Vanja and Göbel, Andreas and Friedrich, Tobias}, booktitle = {Artificial Intelligence and Statistics (AISTATS)}, keywords = {aistats andreasgoebel francescoquinzan tobiasfriedrich vanjadoskoc year2021}, pages = {964-972}, title = {Adaptive Sampling for Fast Constrained Maximization of Submodular Functions}, year = 2021 }
• 
  Khazraei, Ardalan; Kötzing, Timo; Seidel, KarenTowards a Map for Incremental Learning in the Limit from Positive and Negative Information. Computability in Europe (CiE) 2021
  [ BibTeX ]
   
  @inproceedings{khazraei2021towards, author = {Khazraei, Ardalan and Kötzing, Timo and Seidel, Karen}, booktitle = {Computability in Europe (CiE)}, keywords = {ardalankhazraei cie karenseidel timokoetzing year2021}, title = {Towards a Map for Incremental Learning in the Limit from Positive and Negative Information}, year = 2021 }
• 
  Kötzing, Timo; Seidel, KarenLearning Languages in the Limit from Positive Information with Finitely Many Memory Changes. Computability in Europe (CiE) 2021
  [ BibTeX ]
   
  @inproceedings{kotzing2021learning, author = {Kötzing, Timo and Seidel, Karen}, booktitle = {Computability in Europe (CiE)}, keywords = {cie karenseidel timokoetzing year2021}, title = {Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes}, year = 2021 }
• 
  Doskoč, Vanja; Kötzing, TimoNormal Forms for Semantically Witness-Based Learners in Inductive Inference. Computability in Europe (CiE) 2021
  [ BibTeX ]
   
  @inproceedings{doskoc2021normal, author = {Doskoč, Vanja and Kötzing, Timo}, booktitle = {Computability in Europe (CiE)}, keywords = {cie timokoetzing vanjadoskoc year2021}, title = {Normal Forms for Semantically Witness-Based Learners in Inductive Inference}, year = 2021 }
• 
  Doskoč, Vanja; Kötzing, TimoMapping Monotonic Restrictions in Inductive Inference. Computability in Europe (CiE) 2021
  [ BibTeX ]
   
  @inproceedings{doskoc2021mapping, author = {Doskoč, Vanja and Kötzing, Timo}, booktitle = {Computability in Europe (CiE)}, keywords = {cie timokoetzing vanjadoskoc year2021}, title = {Mapping Monotonic Restrictions in Inductive Inference}, year = 2021 }
• 
  Berger, Julian; Böther, Maximilian; Doskoč, Vanja; Gadea Harder, Jonathan; Klodt, Nicolas; Kötzing, Timo; Lötzsch, Winfried; Peters, Jannik; Schiller, Leon; Seifert, Lars; Wells, Armin; Wietheger, SimonLearning Languages with Decidable Hypotheses. Computability in Europe (CiE) 2021
  [ BibTeX ]
   
  @inproceedings{berger2021learning, author = {Berger, Julian and Böther, Maximilian and Doskoč, Vanja and Gadea Harder, Jonathan and Klodt, Nicolas and Kötzing, Timo and Lötzsch, Winfried and Peters, Jannik and Schiller, Leon and Seifert, Lars and Wells, Armin and Wietheger, Simon}, booktitle = {Computability in Europe (CiE)}, keywords = {arminwells cie jannikpeters jonathangadeaharder julianberger larsseifert leonschiller maximilianboether nicolasklodt simonwietheger timokoetzing vanjadoskoc winfriedloetzsch year2021}, title = {Learning Languages with Decidable Hypotheses}, year = 2021 }
• 
  Doerr, Benjamin; Kötzing, TimoLower Bounds from Fitness Levels Made Easy. Genetic and Evolutionary Computation Conference (GECCO) 2021
  [ Abstract ] [ BibTeX ]
   
  One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters gamma. In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1+1) EA on LeadingOnes. (ii) A lower bound for the run time of the (1+1) EA on OneMax, tight apart from an O(n) term. (iii) A lower bound for the run time of the (1+1) EA on long k-paths.
  @inproceedings{doerr2021lower, abstract = {One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters gamma. In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1+1) EA on LeadingOnes. (ii) A lower bound for the run time of the (1+1) EA on OneMax, tight apart from an O(n) term. (iii) A lower bound for the run time of the (1+1) EA on long k-paths.}, author = {Doerr, Benjamin and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {benjamindoerr gecco timokoetzing year2021}, title = {Lower Bounds from Fitness Levels Made Easy}, year = 2021 }
• 
  Böther, Maximilian; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise; Schiller, LeonEvolutionary Minimization of Traffic Congestion. Genetic and Evolutionary Computation Conference (GECCO) 2021
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and a destination and then aims at finding up to \(n\) different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of the city of Berlin, Germany. We find that a combination of all operators yields the best result, improving the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. For the base case \(n=2\), we compare our MREA to the highly tailored optimal solver by Bläsius etal. [ATMOS 2020] and show that, in the median, our approach finds solutions of quality at least \(99.69\%\) of an optimal solution while only requiring \(40\%\) of the time.
  @inproceedings{boether2021evolutionary, abstract = {Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and a destination and then aims at finding up to \(n\) different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of the city of Berlin, Germany. We find that a combination of all operators yields the best result, improving the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. For the base case \(n=2\), we compare our MREA to the highly tailored optimal solver by Bläsius etal. [ATMOS 2020] and show that, in the median, our approach finds solutions of quality at least \(99.69\%\) of an optimal solution while only requiring \(40\%\) of the time.}, author = {Böther, Maximilian and Fischbeck, Philipp and Friedrich, Tobias and Krejca, Martin S. and Molitor, Louise and Schiller, Leon}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco leonschiller louisemolitor martinskrejca maximilianboether philippfischbeck tobiasfriedrich year2021}, title = {Evolutionary Minimization of Traffic Congestion}, year = 2021 }
• 
  Casel, Katrin; Schmid, Markus L.Fine-Grained Complexity of Regular Path Queries. International Conference on Database Theory (ICDT) 2021
  [ Abstract ] [ BibTeX ] [ Download ]
   
  A regular path query (RPQ) is a regular expression \(q\) that returns all node pairs \((u, v)\) from a graph database that are connected by an arbitrary path labelled with a word from \(L(q)\). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for \(q\) and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.
  @inproceedings{casel2021finegrained, abstract = {A regular path query (RPQ) is a regular expression \(q\) that returns all node pairs \((u, v)\) from a graph database that are connected by an arbitrary path labelled with a word from \(L(q)\). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for \(q\) and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.}, author = {Casel, Katrin and Schmid, Markus L.}, booktitle = {International Conference on Database Theory (ICDT)}, keywords = {icdt katrincasel markuslschmid year2021}, title = {Fine-Grained Complexity of Regular Path Queries}, year = 2021 }
• 
  Kißig, Otto; Taraz, Martin; Cohen, Sarel; Doskoč, Vanja; Friedrich, TobiasDrug Repurposing for Multiple COVID Strains using Collaborative Filtering. ICLR Workshop on Machine Learning for Preventing and Combating Pandemics (MLPCP@ICLR) 2021
  [ BibTeX ]
   
  @inproceedings{kissig2021repurposing, author = {Kißig, Otto and Taraz, Martin and Cohen, Sarel and Doskoč, Vanja and Friedrich, Tobias}, booktitle = {ICLR Workshop on Machine Learning for Preventing and Combating Pandemics (MLPCP@ICLR)}, keywords = {martintaraz mlpcp@iclr ottokissig sarelcohen tobiasfriedrich vanjadoskoc year2021}, title = {Drug Repurposing for Multiple COVID Strains using Collaborative Filtering}, year = 2021 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, MaximilianForce-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane. Symposium on Experimental Algorithms (SEA) 2021
  [ Abstract ] [ BibTeX ]
   
  Force-directed drawing algorithms are the most commonly used approach to visualize networks. While they are usually very robust, the performance of Euclidean spring embedders decreases if the graph exhibits the high level of heterogeneity that typically occurs in scale-free real-world networks. As heterogeneity naturally emerges from hyperbolic geometry (in fact, scale-free networks are often perceived to have an underlying hyperbolic geometry), it is natural to embed them into the hyperbolic plane instead. Previous techniques that produce hyperbolic embeddings usually make assumptions about the given network, which (if not met) impairs the quality of the embedding. It is still an open problem to adapt force-directed embedding algorithms to make use of the heterogeneity of the hyperbolic plane, while also preserving their robustness. We identify fundamental differences between the behavior of spring embedders in Euclidean and hyperbolic space, and adapt the technique to take advantage of the heterogeneity of the hyperbolic plane.
  @inproceedings{bfk-fdesfnhp-2021, abstract = {Force-directed drawing algorithms are the most commonly used approach to visualize networks. While they are usually very robust, the performance of Euclidean spring embedders decreases if the graph exhibits the high level of heterogeneity that typically occurs in scale-free real-world networks. As heterogeneity naturally emerges from hyperbolic geometry (in fact, scale-free networks are often perceived to have an underlying hyperbolic geometry), it is natural to embed them into the hyperbolic plane instead. Previous techniques that produce hyperbolic embeddings usually make assumptions about the given network, which (if not met) impairs the quality of the embedding. It is still an open problem to adapt force-directed embedding algorithms to make use of the heterogeneity of the hyperbolic plane, while also preserving their robustness. We identify fundamental differences between the behavior of spring embedders in Euclidean and hyperbolic space, and adapt the technique to take advantage of the heterogeneity of the hyperbolic plane.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian}, booktitle = {Symposium on Experimental Algorithms (SEA)}, keywords = {maximiliankatzmann sea thomasblaesius tobiasfriedrich year2021}, title = {Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane}, year = 2021 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, RalfThe Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability. Symposium on Discrete Algorithms (SODA) 2021: 42-53
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.
  @inproceedings{blasius2021impact, abstract = {Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.}, author = {Bläsius, Thomas and Friedrich, Tobias and Göbel, Andreas and Levy, Jordi and Rothenberger, Ralf}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {andreasgoebel jordilevy ralfrothenberger sat soda thomasblaesius tobiasfriedrich year2021}, pages = {42-53}, publisher = {SIAM}, title = {The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability}, year = 2021 }

2021

• 
  Cseh, Ágnes; Juhos, AttilaPairwise Preferences in the Stable Marriage Problem. ACM Transactions on Economics and Computation (TEAC) 2021: 1--28
  [ BibTeX ] [ Download ]
   
  @article{cseh2021pairwise, author = {Cseh, Ágnes and Juhos, Attila}, journal = {ACM Transactions on Economics and Computation (TEAC)}, keywords = {sys:relevantfor:ae agnescseh}, number = 1, pages = {1–28}, publisher = {ACM New York, NY, USA}, title = {Pairwise Preferences in the Stable Marriage Problem}, volume = 9, year = 2021 }
• 
  Cseh, Ágnes; Kavitha, TelikepalliPopular matchings in complete graphs. Algorithmica 2021: 1--31
  [ BibTeX ] [ URL ]
   
  @article{cseh2021popular, author = {Cseh, Ágnes and Kavitha, Telikepalli}, journal = {Algorithmica}, keywords = {sys:relevantfor:ae agnescseh}, pages = {1–31}, publisher = {Springer}, title = {Popular matchings in complete graphs}, year = 2021 }
• 
  Andersson, Tommy; Cseh, Ágnes; Ehlers, Lars; Erlanson, AlbinOrganizing time exchanges: Lessons from matching markets. American Economic Journal: Microeconomics 2021: 338--73
  [ BibTeX ] [ Download ]
   
  @article{andersson2021organizing, author = {Andersson, Tommy and Cseh, Ágnes and Ehlers, Lars and Erlanson, Albin}, journal = {American Economic Journal: Microeconomics}, keywords = {sys:relevantfor:ae agnescseh}, number = 1, pages = {338–73}, title = {Organizing time exchanges: Lessons from matching markets}, volume = 13, year = 2021 }
• 
  Friedemann, Wilhelm; Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna; Peters, Jannik; Stephan, Daniel; Vaichenker, MichaelEfficiency and Stability in Euclidean Network Design. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2021
  [ BibTeX ]
   
  @article{friedemann2021efficiency, author = {Friedemann, Wilhelm and Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna and Peters, Jannik and Stephan, Daniel and Vaichenker, Michael}, journal = {Symposium on Parallelism in Algorithms and Architectures (SPAA)}, keywords = {annamelnichenko pascallenzner spaa tobiasfriedrich year2021}, title = {Efficiency and Stability in Euclidean Network Design}, year = 2021 }
• 
  Doerr, Benjamin; Krejca, Martin S.A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes. Theoretical Computer Science 2021: 121-128
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  With elementary means, we prove in this note a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size \(\mu\) is at least \(128 n \ln(n)\) and the selection rate \(\mu/\lambda\) is at most some constant less than \(\frac{1}{4e \approx 0.092\), then the UMDA samples the optimum within \(O\big(n\frac{\lambda}{log (\lambda/\mu)}\big)\) fitness evaluations with high probability. This improves over the previous \(O(n \lambda \log\lambda)\) guarantee that was obtained by Dang and Lehre (2015) via the deep level-based population method. With similar arguments as in our upper-bound analysis, we also obtain the first lower bound for this problem. Under similar assumptions, we prove that a bound of \(\Omega\big(lambda \frac{n - \log(n\lambda)}log (\lambda / \mu)}\big)\) fitness evaluations holds with high probability.
  @article{doerr2021simplified, abstract = {With elementary means, we prove in this note a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size \(\mu\) is at least \(128 n \ln(n)\) and the selection rate \(\mu/\lambda\) is at most some constant less than \(\frac{1}{4e} \approx 0.092\), then the UMDA samples the optimum within \(O\big(n\frac{\lambda}{\log (\lambda/\mu)}\big)\) fitness evaluations with high probability. This improves over the previous \(O(n \lambda \log\lambda)\) guarantee that was obtained by Dang and Lehre (2015) via the deep level-based population method. With similar arguments as in our upper-bound analysis, we also obtain the first lower bound for this problem. Under similar assumptions, we prove that a bound of \(\Omega\big(\lambda \frac{n - \log(n\lambda)}{\log (\lambda / \mu)}\big)\) fitness evaluations holds with high probability.}, author = {Doerr, Benjamin and Krejca, Martin S.}, journal = {Theoretical Computer Science}, keywords = {benjamindoerr martinskrejca tcs year2021}, pages = {121-128}, title = {A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes}, volume = 851, year = 2021 }
• 
  Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L.On the Complexity of the Smallest Grammar Problem over Fixed Alphabets. Theory of Computing Systems 2021: 344–409
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  In the smallest grammar problem, we are given a word \(w\)and we want to compute a preferably small context-free grammar \(G\) for the singleton language \(\{w\}\) (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is \(\mathsf{NP}\)-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless \(\mathsf{P}\) = \(\mathsf{NP}\). We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains \(\mathsf{NP}\)-complete (and its optimisation version is \(\mathsf{APX}\)-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i.e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields \(\mathsf{W}\)[1]-hardness. Furthermore, we present an \(O(3^{|w|})\) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i.e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the ``hierarchical depth'' of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.
  @article{casel2020article, abstract = {In the smallest grammar problem, we are given a word \(w\)and we want to compute a preferably small context-free grammar \(G\) for the singleton language \(\{w\}\) (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is \(\mathsf{NP}\)-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless \(\mathsf{P}\) = \(\mathsf{NP}\). We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains \(\mathsf{NP}\)-complete (and its optimisation version is \(\mathsf{APX}\)-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i.e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields \(\mathsf{W}\)[1]-hardness. Furthermore, we present an \(O(3^{|w|})\) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i.e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the ``hierarchical depth'' of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.}, author = {Casel, Katrin and Fernau, Henning and Gaspers, Serge and Gras, Benjamin and Schmid, Markus L.}, editor = {Springer}, journal = {Theory of Computing Systems}, keywords = {benjamingras henningfernau katrincasel markuslschmid sergegaspers tocs year2020}, number = 2, pages = {344–409}, title = {On the Complexity of the Smallest Grammar Problem over Fixed Alphabets}, volume = 65, year = 2021 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Complexity of Dependency Detection and Discovery in Relational Databases. CoRR 2021

  ArXiv preprint
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.
  @article{blasius2021detectiondiscovery, abstract = {Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.}, author = {Bläsius, Thomas and Friedrich, Tobias and Schirneck, Martin}, journal = {CoRR}, keywords = {arxiv martinschirneck thomasblaesius tobiasfriedrich year2021}, note = {ArXiv preprint}, title = {The Complexity of Dependency Detection and Discovery in Relational Databases}, volume = {arXiv:2103.13331}, year = 2021 }