150 Search Results for "M�ller-Gronbach, Thomas"

Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.79
Application of GIS in Public Health Practice: A Consortium’s Approach to Tackling Travel Delays in Obstetric Emergencies in Urban Areas (Short Paper)

Authors: Jia Wang, Itohan Osayande, Peter M. Macharia, Prestige Tatenda Makanga, Kerry L. M. Wong, Tope Olubodun, Uchenna Gwacham-Anisiobi, Olakunmi Ogunyemi, Abimbola Olaniran, Ibukun-Oluwa O. Abejirinde, Lenka Beňová, Bosede B. Afolabi, and Aduragbemi Banke-Thomas

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Geographic Information System (GIS) has become an effective and reliable tool for researchers, policymakers, and decision-makers to map health outcomes and inform targeted planning, evaluation, and monitoring. With the advent of big data-enabled GIS, researchers can now identify disparities and spatial inequalities in health at more granular levels, enabling them to provide more accurate and robust services and products for healthcare. This paper aims to showcase the progress of the On Tackling In-transit Delays for Mothers in Emergency (OnTIME) project, which is a unique collaborative effort between academia, policymakers, and industrial partners. The paper demonstrates how the limitations of traditional spatial accessibility models and data gaps have been overcome by combining GIS and big data to map the geographic accessibility and coverage of health facilities capable of providing emergency obstetric care (EmOC) in conurbations in Africa. The OnTIME project employs various GIS technologies and concepts, such as big spatial data, spatial databases, and public participation geographic information systems (PPGIS). We provide an overview of these concepts in relation to the OnTIME project to demonstrate the application of GIS in public health practice.
Cite as

Jia Wang, Itohan Osayande, Peter M. Macharia, Prestige Tatenda Makanga, Kerry L. M. Wong, Tope Olubodun, Uchenna Gwacham-Anisiobi, Olakunmi Ogunyemi, Abimbola Olaniran, Ibukun-Oluwa O. Abejirinde, Lenka Beňová, Bosede B. Afolabi, and Aduragbemi Banke-Thomas. Application of GIS in Public Health Practice: A Consortium’s Approach to Tackling Travel Delays in Obstetric Emergencies in Urban Areas (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 79:1-79:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.GIScience.2023.79,
  author =	{Wang, Jia and Osayande, Itohan and Macharia, Peter M. and Makanga, Prestige Tatenda and Wong, Kerry L. M. and Olubodun, Tope and Gwacham-Anisiobi, Uchenna and Ogunyemi, Olakunmi and Olaniran, Abimbola and Abejirinde, Ibukun-Oluwa O. and Be\v{n}ov\'{a}, Lenka and Afolabi, Bosede B. and Banke-Thomas, Aduragbemi},
  title =	{{Application of GIS in Public Health Practice: A Consortium’s Approach to Tackling Travel Delays in Obstetric Emergencies in Urban Areas}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{79:1--79:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.79},
  URN =		{urn:nbn:de:0030-drops-189748},
  doi =		{10.4230/LIPIcs.GIScience.2023.79},
  annote =	{Keywords: GIS, Public Health, Accessibility, OnTIME, EmOC, Public Participation GIS, Big Data, Google}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.43
Reconfiguration of Digraph Homomorphisms

Authors: Benjamin Lévêque, Moritz Mühlenthaler, and Thomas Suzan

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
For a fixed graph H, the H-Recoloring problem asks whether, given two homomorphisms from a graph G to H, one homomorphism can be transformed into the other by changing the image of a single vertex in each step and maintaining a homomorphism to H throughout. The most general algorithmic result for H-Recoloring so far has been proposed by Wrochna in 2014, who introduced a topological approach to obtain a polynomial-time algorithm for any undirected loopless square-free graph H. We show that the topological approach can be used to recover essentially all previous algorithmic results for H-Recoloring and that it is applicable also in the more general setting of digraph homomorphisms. In particular, we show that H-Recoloring admits a polynomial-time algorithm i) if H is a loopless digraph that does not contain a 4-cycle of algebraic girth 0 and ii) if H is a reflexive digraph that contains no triangle of algebraic girth 1 and no 4-cycle of algebraic girth 0.
Cite as

Benjamin Lévêque, Moritz Mühlenthaler, and Thomas Suzan. Reconfiguration of Digraph Homomorphisms. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 43:1-43:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{leveque_et_al:LIPIcs.STACS.2023.43,
  author =	{L\'{e}v\^{e}que, Benjamin and M\"{u}hlenthaler, Moritz and Suzan, Thomas},
  title =	{{Reconfiguration of Digraph Homomorphisms}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{43:1--43:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.43},
  URN =		{urn:nbn:de:0030-drops-176958},
  doi =		{10.4230/LIPIcs.STACS.2023.43},
  annote =	{Keywords: Digraph Homomorphisms, Combinatorial Reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.45
Tight Bounds for Repeated Balls-Into-Bins

Authors: Dimitrios Los and Thomas Sauerwald

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
We study the repeated balls-into-bins process introduced by Becchetti, Clementi, Natale, Pasquale and Posta (2019). This process starts with m balls arbitrarily distributed across n bins. At each round t = 1,2,…, one ball is selected from each non-empty bin, and then placed it into a bin chosen independently and uniformly at random. We prove the following results: - For any n ⩽ m ⩽ poly(n), we prove a lower bound of Ω(m/n ⋅ log n) on the maximum load. For the special case m = n, this matches the upper bound of 𝒪(log n), as shown in [Luca Becchetti et al., 2019]. It also provides a positive answer to the conjecture in [Luca Becchetti et al., 2019] that for m = n the maximum load is ω(log n/ log log n) at least once in a polynomially large time interval. For m ∈ [ω(n), n log n], our new lower bound disproves the conjecture in [Luca Becchetti et al., 2019] that the maximum load remains 𝒪(log n). - For any n ⩽ m ⩽ poly(n), we prove an upper bound of 𝒪(m/n ⋅ log n) on the maximum load for all steps of a polynomially large time interval. This matches our lower bound up to multiplicative constants. - For any m ⩾ n, our analysis also implies an 𝒪(m²/n) waiting time to reach a configuration with a 𝒪(m/n ⋅ log m) maximum load, even for worst-case initial distributions. - For m ⩾ n, we show that every ball visits every bin in 𝒪(m log m) rounds. For m = n, this improves the previous upper bound of 𝒪(n log² n) in [Luca Becchetti et al., 2019]. We also prove that the upper bound is tight up to multiplicative constants for any n ⩽ m ⩽ poly(n).
Cite as

Dimitrios Los and Thomas Sauerwald. Tight Bounds for Repeated Balls-Into-Bins. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 45:1-45:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{los_et_al:LIPIcs.STACS.2023.45,
  author =	{Los, Dimitrios and Sauerwald, Thomas},
  title =	{{Tight Bounds for Repeated Balls-Into-Bins}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{45:1--45:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.45},
  URN =		{urn:nbn:de:0030-drops-176975},
  doi =		{10.4230/LIPIcs.STACS.2023.45},
  annote =	{Keywords: Repeated balls-into-bins, self-stabilizing systems, balanced allocations, potential functions, random walks}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.13
Computation of Cycle Bases in Surface Embedded Graphs

Authors: Kyle Fox and Thomas Stanley

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We present an O(n³ g²log g + m) + Õ(n^{ω + 1}) time deterministic algorithm to find the minimum cycle basis of a directed graph embedded on an orientable surface of genus g. This result improves upon the previous fastest known running time of O(m³n + m²n² log n) applicable to general directed graphs. While an O(n^ω + 2^{2g}n² + m) time deterministic algorithm was known for undirected graphs, the use of the underlying field ℚ in the directed case (as opposed to ℤ₂ for the undirected case) presents extra challenges. It turns out that some of our new observations are useful for both variants of the problem, so we present an O(n^ω + n² g² log g + m) time deterministic algorithm for undirected graphs as well.
Cite as

Kyle Fox and Thomas Stanley. Computation of Cycle Bases in Surface Embedded Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.ISAAC.2022.13,
  author =	{Fox, Kyle and Stanley, Thomas},
  title =	{{Computation of Cycle Bases in Surface Embedded Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.13},
  URN =		{urn:nbn:de:0030-drops-172982},
  doi =		{10.4230/LIPIcs.ISAAC.2022.13},
  annote =	{Keywords: cycle basis, surface embedded graphs, homology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.1
Tiling with Squares and Packing Dominos in Polynomial Time

Authors: Anders Aamand, Mikkel Abrahamsen, Thomas Ahle, and Peter M. R. Rasmussen

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
A polyomino is a polygonal region with axis-parallel edges and corners of integral coordinates, which may have holes. In this paper, we consider planar tiling and packing problems with polyomino pieces and a polyomino container P. We give polynomial-time algorithms for deciding if P can be tiled with k× k squares for any fixed k which can be part of the input (that is, deciding if P is the union of a set of non-overlapping k× k squares) and for packing P with a maximum number of non-overlapping and axis-parallel 2× 1 dominos, allowing rotations by 90^∘. As packing is more general than tiling, the latter algorithm can also be used to decide if P can be tiled by 2× 1 dominos. These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of 2× 2 squares is known to be NP-hard [J. Algorithms 1990]. For our three problems there are known pseudo-polynomial-time algorithms, that is, algorithms with running times polynomial in the area or perimeter of P. However, the standard, compact way to represent a polygon is by listing the coordinates of the corners in binary. We use this representation, and thus present the first polynomial-time algorithms for the problems. Concretely, we give a simple O(nlog n)-time algorithm for tiling with squares, where n is the number of corners of P. We then give a more involved algorithm that reduces the problems of packing and tiling with dominos to finding a maximum and perfect matching in a graph with O(n³) vertices. This leads to algorithms with running times O(n³(log³ n)/(log²log n)) and O(n³(log² n)/(log log n)), respectively.
Cite as

Anders Aamand, Mikkel Abrahamsen, Thomas Ahle, and Peter M. R. Rasmussen. Tiling with Squares and Packing Dominos in Polynomial Time. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.SoCG.2022.1,
  author =	{Aamand, Anders and Abrahamsen, Mikkel and Ahle, Thomas and Rasmussen, Peter M. R.},
  title =	{{Tiling with Squares and Packing Dominos in Polynomial Time}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.1},
  URN =		{urn:nbn:de:0030-drops-160096},
  doi =		{10.4230/LIPIcs.SoCG.2022.1},
  annote =	{Keywords: packing, tiling, polyominos}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.103
Balanced Allocations with Incomplete Information: The Power of Two Queries

Authors: Dimitrios Los and Thomas Sauerwald

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We consider the allocation of m balls into n bins with incomplete information. In the classical Two-Choice process a ball first queries the load of two randomly chosen bins and is then placed in the least loaded bin. In our setting, each ball also samples two random bins but can only estimate a bin’s load by sending binary queries of the form "Is the load at least the median?" or "Is the load at least 100?". For the lightly loaded case m = 𝒪(n), Feldheim and Gurel-Gurevich (2021) showed that with one query it is possible to achieve a maximum load of 𝒪(√{log n/log log n}), and they also pose the question whether a maximum load of m/n+𝒪(√{log n/log log n}) is possible for any m = Ω(n). In this work, we resolve this open problem by proving a lower bound of m/n+Ω(√{log n}) for a fixed m = Θ(n √{log n}), and a lower bound of m/n+Ω(log n/log log n) for some m depending on the used strategy. We complement this negative result by proving a positive result for multiple queries. In particular, we show that with only two binary queries per chosen bin, there is an oblivious strategy which ensures a maximum load of m/n+𝒪(√{log n}) for any m ≥ 1. Further, for any number of k = 𝒪(log log n) binary queries, the upper bound on the maximum load improves to m/n + 𝒪(k(log n)^{1/k}) for any m ≥ 1. This result for k queries has several interesting consequences: (i) it implies new bounds for the (1+β)-process introduced by Peres, Talwar and Wieder (2015), (ii) it leads to new bounds for the graphical balanced allocation process on dense expander graphs, and (iii) it recovers and generalizes the bound of m/n+𝒪(log log n) on the maximum load achieved by the Two-Choice process, including the heavily loaded case m = Ω(n) which was derived in previous works by Berenbrink et al. (2006) as well as Talwar and Wieder (2014). One novel aspect of our proofs is the use of multiple super-exponential potential functions, which might be of use in future work.
Cite as

Dimitrios Los and Thomas Sauerwald. Balanced Allocations with Incomplete Information: The Power of Two Queries. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 103:1-103:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{los_et_al:LIPIcs.ITCS.2022.103,
  author =	{Los, Dimitrios and Sauerwald, Thomas},
  title =	{{Balanced Allocations with Incomplete Information: The Power of Two Queries}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{103:1--103:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.103},
  URN =		{urn:nbn:de:0030-drops-156994},
  doi =		{10.4230/LIPIcs.ITCS.2022.103},
  annote =	{Keywords: power-of-two-choices, balanced allocations, potential functions, thinning}
}
Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2021.19
A Column Generation-Based Heuristic for the Line Planning Problem with Service Levels (Short Paper)

Authors: Hector Gatt, Jean-Marie Freche, Fabien Lehuédé, and Thomas G. Yeung

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
This paper addresses the line planning problem by the combination of existing models reinforced with realistic characteristics like lines frequencies intervals or maximum number of lines, useful for public transportation companies. The problem is solved by an innovative, easily implementable, heuristic combining column generation and elementary column enumeration methods. In this paper, the operator’s exploitation costs are minimized while respecting new quality of service parameters addressed to passengers. Furthermore, a case study based on a real network is performed and described in this paper to prove the efficiency of our method.
Cite as

Hector Gatt, Jean-Marie Freche, Fabien Lehuédé, and Thomas G. Yeung. A Column Generation-Based Heuristic for the Line Planning Problem with Service Levels (Short Paper). In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 19:1-19:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gatt_et_al:OASIcs.ATMOS.2021.19,
  author =	{Gatt, Hector and Freche, Jean-Marie and Lehu\'{e}d\'{e}, Fabien and Yeung, Thomas G.},
  title =	{{A Column Generation-Based Heuristic for the Line Planning Problem with Service Levels}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{19:1--19:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.19},
  URN =		{urn:nbn:de:0030-drops-148885},
  doi =		{10.4230/OASIcs.ATMOS.2021.19},
  annote =	{Keywords: Line Planning, Network Design, Column Generation, Service Performance}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.20
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry

Authors: Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing non-optimal outputs) for an improved running time. For the vertex cover problem, there is a gap between theory and practice when it comes to understanding this tradeoff. On the one hand, it is known that it is NP-hard to approximate a minimum vertex cover within a factor of √2. On the other hand, a simple greedy algorithm yields close to optimal approximations in practice. A promising approach towards understanding this discrepancy is to recognize the differences between theoretical worst-case instances and real-world networks. Following this direction, we close the gap between theory and practice by providing an algorithm that efficiently computes nearly optimal vertex cover approximations on hyperbolic random graphs; a network model that closely resembles real-world networks in terms of degree distribution, clustering, and the small-world property. More precisely, our algorithm computes a (1 + o(1))-approximation, asymptotically almost surely, and has a running time of 𝒪(m log(n)). The proposed algorithm is an adaption of the successful greedy approach, enhanced with a procedure that improves on parts of the graph where greedy is not optimal. This makes it possible to introduce a parameter that can be used to tune the tradeoff between approximation performance and running time. Our empirical evaluation on real-world networks shows that this allows for improving over the near-optimal results of the greedy approach.
Cite as

Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2021.20,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Katzmann, Maximilian},
  title =	{{Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.20},
  URN =		{urn:nbn:de:0030-drops-146012},
  doi =		{10.4230/LIPIcs.ESA.2021.20},
  annote =	{Keywords: vertex cover, approximation, random graphs, hyperbolic geometry, efficient algorithm}
}
Document
DOI: 10.4230/OASIcs.LDK.2021.37
A Review and Cluster Analysis of German Polarity Resources for Sentiment Analysis

Authors: Bettina M. J. Kern, Andreas Baumann, Thomas E. Kolb, Katharina Sekanina, Klaus Hofmann, Tanja Wissik, and Julia Neidhardt

Published in: OASIcs, Volume 93, 3rd Conference on Language, Data and Knowledge (LDK 2021)

Abstract
The domain of German polarity dictionaries is heterogeneous with many small dictionaries created for different purposes and using different methods. This paper aims to map out the landscape of freely available German polarity dictionaries by clustering them to uncover similarities and shared features. We find that, although most dictionaries seem to agree in their assessment of a word’s sentiment, subsets of them form groups of interrelated dictionaries. These dependencies are in most cases an immediate reflex of how these dictionaries were designed and compiled. As a consequence, we argue that sentiment evaluation should be based on multiple and diverse sentiment resources in order to avoid error propagation and amplification of potential biases.
Cite as

Bettina M. J. Kern, Andreas Baumann, Thomas E. Kolb, Katharina Sekanina, Klaus Hofmann, Tanja Wissik, and Julia Neidhardt. A Review and Cluster Analysis of German Polarity Resources for Sentiment Analysis. In 3rd Conference on Language, Data and Knowledge (LDK 2021). Open Access Series in Informatics (OASIcs), Volume 93, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kern_et_al:OASIcs.LDK.2021.37,
  author =	{Kern, Bettina M. J. and Baumann, Andreas and Kolb, Thomas E. and Sekanina, Katharina and Hofmann, Klaus and Wissik, Tanja and Neidhardt, Julia},
  title =	{{A Review and Cluster Analysis of German Polarity Resources for Sentiment Analysis}},
  booktitle =	{3rd Conference on Language, Data and Knowledge (LDK 2021)},
  pages =	{37:1--37:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-199-3},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{93},
  editor =	{Gromann, Dagmar and S\'{e}rasset, Gilles and Declerck, Thierry and McCrae, John P. and Gracia, Jorge and Bosque-Gil, Julia and Bobillo, Fernando and Heinisch, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.LDK.2021.37},
  URN =		{urn:nbn:de:0030-drops-145734},
  doi =		{10.4230/OASIcs.LDK.2021.37},
  annote =	{Keywords: cluster analysis, sentiment polarity, sentiment analysis, German, review}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.27
Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries

Authors: Thomas Erlebach, Michael Hoffmann, and Murilo Santos de Lima

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
The area of computing with uncertainty considers problems where some information about the input elements is uncertain, but can be obtained using queries. For example, instead of the weight of an element, we may be given an interval that is guaranteed to contain the weight, and a query can be performed to reveal the weight. While previous work has considered models where queries are asked either sequentially (adaptive model) or all at once (non-adaptive model), and the goal is to minimize the number of queries that are needed to solve the given problem, we propose and study a new model where k queries can be made in parallel in each round, and the goal is to minimize the number of query rounds. We use competitive analysis and present upper and lower bounds on the number of query rounds required by any algorithm in comparison with the optimal number of query rounds. Given a set of uncertain elements and a family of m subsets of that set, we present an algorithm for determining the value of the minimum of each of the subsets that requires at most (2+ε) ⋅ opt_k+O(1/(ε) ⋅ lg m) rounds for every 0 < ε < 1, where opt_k is the optimal number of rounds, as well as nearly matching lower bounds. For the problem of determining the i-th smallest value and identifying all elements with that value in a set of uncertain elements, we give a 2-round-competitive algorithm. We also show that the problem of sorting a family of sets of uncertain elements admits a 2-round-competitive algorithm and this is the best possible.
Cite as

Thomas Erlebach, Michael Hoffmann, and Murilo Santos de Lima. Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.STACS.2021.27,
  author =	{Erlebach, Thomas and Hoffmann, Michael and de Lima, Murilo Santos},
  title =	{{Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.27},
  URN =		{urn:nbn:de:0030-drops-136728},
  doi =		{10.4230/LIPIcs.STACS.2021.27},
  annote =	{Keywords: online algorithms, competitive analysis, explorable uncertainty, parallel algorithms, minimum problem, selection problem}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.21
The Minimization of Random Hypergraphs

Authors: Thomas Bläsius, Tobias Friedrich, and Martin Schirneck

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We investigate the maximum-entropy model B_{n,m,p} for random n-vertex, m-edge multi-hypergraphs with expected edge size pn. We show that the expected size of the minimization min(B_{n,m,p}), i.e., the number of inclusion-wise minimal edges of B_{n,m,p}, undergoes a phase transition with respect to m. If m is at most 1/(1-p)^{(1-p)n}, then E[|min(B_{n,m,p})|] is of order Θ(m), while for m ≥ 1/(1-p)^{(1-p+ε)n} for any ε > 0, it is Θ(2^{(H(α) + (1-α) log₂ p) n}/√n). Here, H denotes the binary entropy function and α = - (log_{1-p} m)/n. The result implies that the maximum expected number of minimal edges over all m is Θ((1+p)ⁿ/√n). Our structural findings have algorithmic implications for minimizing an input hypergraph. This has applications in the profiling of relational databases as well as for the Orthogonal Vectors problem studied in fine-grained complexity. We make several technical contributions that are of independent interest in probability. First, we improve the Chernoff-Hoeffding theorem on the tail of the binomial distribution. In detail, we show that for a binomial variable Y ∼ Bin(n,p) and any 0 < x < p, it holds that P[Y ≤ xn] = Θ(2^{-D(x‖p) n}/√n), where D is the binary Kullback-Leibler divergence between Bernoulli distributions. We give explicit upper and lower bounds on the constants hidden in the big-O notation that hold for all n. Secondly, we establish the fact that the probability of a set of cardinality i being minimal after m i.i.d. maximum-entropy trials exhibits a sharp threshold behavior at i^* = n + log_{1-p} m.
Cite as

Thomas Bläsius, Tobias Friedrich, and Martin Schirneck. The Minimization of Random Hypergraphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2020.21,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Schirneck, Martin},
  title =	{{The Minimization of Random Hypergraphs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.21},
  URN =		{urn:nbn:de:0030-drops-128871},
  doi =		{10.4230/LIPIcs.ESA.2020.21},
  annote =	{Keywords: Chernoff-Hoeffding theorem, maximum entropy, maximization, minimization, phase transition, random hypergraphs}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.7
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Authors: Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Laurent polynomials (i.e., polynomials with positive and negative integer exponents). Specifically, we resolve the complexity of approximate counting, the problem of multiplicatively estimating the size of a nonempty set S ⊆ [N], in two natural generalizations of quantum query complexity. Our first result holds in the standard Quantum Merlin - Arthur (QMA) setting, in which a quantum algorithm receives an untrusted quantum witness. We show that, if the algorithm makes T quantum queries to S, and also receives an (untrusted) m-qubit quantum witness, then either m = Ω(|S|) or T = Ω(√{N/|S|}). This is optimal, matching the straightforward protocols where the witness is either empty, or specifies all the elements of S. As a corollary, this resolves the open problem of giving an oracle separation between SBP, the complexity class that captures approximate counting, and QMA. In our second result, we ask what if, in addition to a membership oracle for S, a quantum algorithm is also given "QSamples" - i.e., copies of the state |S⟩ = 1/√|S| ∑_{i ∈ S} |i⟩ - or even access to a unitary transformation that enables QSampling? We show that, even then, the algorithm needs either Θ(√{N/|S|}) queries or else Θ(min{|S|^{1/3},√{N/|S|}}) QSamples or accesses to the unitary. Our lower bounds in both settings make essential use of Laurent polynomials, but in different ways.
Cite as

Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 7:1-7:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.CCC.2020.7,
  author =	{Aaronson, Scott and Kothari, Robin and Kretschmer, William and Thaler, Justin},
  title =	{{Quantum Lower Bounds for Approximate Counting via Laurent Polynomials}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{7:1--7:47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.7},
  URN =		{urn:nbn:de:0030-drops-125593},
  doi =		{10.4230/LIPIcs.CCC.2020.7},
  annote =	{Keywords: Approximate counting, Laurent polynomials, QSampling, query complexity}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2020.16
A Profunctorial Scott Semantics

Authors: Zeinab Galal

Published in: LIPIcs, Volume 167, 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)

Abstract
In this paper, we study the bicategory of profunctors with the free finite coproduct pseudo-comonad and show that it constitutes a model of linear logic that generalizes the Scott model. We formalize the connection between the two models as a change of base for enriched categories which induces a pseudo-functor that preserves all the linear logic structure. We prove that morphisms in the co-Kleisli bicategory correspond to the concept of strongly finitary functors (sifted colimits preserving functors) between presheaf categories. We further show that this model provides solutions of recursive type equations which provides 2-dimensional models of the pure lambda calculus and we also exhibit a fixed point operator on terms.
Cite as

Zeinab Galal. A Profunctorial Scott Semantics. In 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 167, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{galal:LIPIcs.FSCD.2020.16,
  author =	{Galal, Zeinab},
  title =	{{A Profunctorial Scott Semantics}},
  booktitle =	{5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-155-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{167},
  editor =	{Ariola, Zena M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2020.16},
  URN =		{urn:nbn:de:0030-drops-123387},
  doi =		{10.4230/LIPIcs.FSCD.2020.16},
  annote =	{Keywords: Linear Logic, Scott Semantics, Profunctors}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2020.25
A Gentzen-Style Monadic Translation of Gödel’s System T

Authors: Chuangjie Xu

Published in: LIPIcs, Volume 167, 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)

Abstract
We introduce a syntactic translation of Gödel’s System 𝖳 parametrized by a weak notion of a monad, and prove a corresponding fundamental theorem of logical relation. Our translation structurally corresponds to Gentzen’s negative translation of classical logic. By instantiating the monad and the logical relation, we reveal the well-known properties and structures of 𝖳-definable functionals including majorizability, continuity and bar recursion. Our development has been formalized in the Agda proof assistant.
Cite as

Chuangjie Xu. A Gentzen-Style Monadic Translation of Gödel’s System T. In 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 167, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{xu:LIPIcs.FSCD.2020.25,
  author =	{Xu, Chuangjie},
  title =	{{A Gentzen-Style Monadic Translation of G\"{o}del’s System T}},
  booktitle =	{5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-155-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{167},
  editor =	{Ariola, Zena M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2020.25},
  URN =		{urn:nbn:de:0030-drops-123472},
  doi =		{10.4230/LIPIcs.FSCD.2020.25},
  annote =	{Keywords: monadic translation, G\"{o}del’s System T, logical relation, negative translation, majorizability, continuity, bar recursion, Agda}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2020.10
Cybersecurity Games for Secure Programming Education in the Industry: Gameplay Analysis

Authors: Tiago Gasiba, Ulrike Lechner, Filip Rezabek, and Maria Pinto-Albuquerque

Published in: OASIcs, Volume 81, First International Computer Programming Education Conference (ICPEC 2020)

Abstract
To minimize the possibility of introducing vulnerabilities in source code, software developers may attend security awareness and secure coding training. From the various approaches of how to raise awareness and adherence to coding standards, one promising novel approach is Cybersecurity Challenges. However, in an industrial setting, time is a precious resource, and, therefore, one needs to understand how to optimize the gaming experience of Cybersecurity Challenges and the effect of this game on secure coding skills. This work identifies the time spent solving challenges of different categories, analyzes gaming strategies in terms of a slow and fast team profile, and relates these profiles to the game success. First results indicate that the slow strategy is more successful than the fast approach. The authors also analyze the possible implications in the design and the training of secure coding in an industrial setting by means of Cybersecurity Challenges. This work concludes with a brief overview of its limitations and next steps in the study.
Cite as

Tiago Gasiba, Ulrike Lechner, Filip Rezabek, and Maria Pinto-Albuquerque. Cybersecurity Games for Secure Programming Education in the Industry: Gameplay Analysis. In First International Computer Programming Education Conference (ICPEC 2020). Open Access Series in Informatics (OASIcs), Volume 81, pp. 10:1-10:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gasiba_et_al:OASIcs.ICPEC.2020.10,
  author =	{Gasiba, Tiago and Lechner, Ulrike and Rezabek, Filip and Pinto-Albuquerque, Maria},
  title =	{{Cybersecurity Games for Secure Programming Education in the Industry: Gameplay Analysis}},
  booktitle =	{First International Computer Programming Education Conference (ICPEC 2020)},
  pages =	{10:1--10:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-153-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{81},
  editor =	{Queir\'{o}s, Ricardo and Portela, Filipe and Pinto, M\'{a}rio and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2020.10},
  URN =		{urn:nbn:de:0030-drops-122977},
  doi =		{10.4230/OASIcs.ICPEC.2020.10},
  annote =	{Keywords: education, training, secure coding, industry, cybersecurity, capture-the-flag, game analysis, cybersecurity challenge}
}
  • Refine by Author
  • 5 Müller-Gronbach, Thomas
  • 4 Henzinger, Thomas A.
  • 4 Novak, Erich
  • 4 Sauerwald, Thomas
  • 3 Erlebach, Thomas
  • Show More...

  • Refine by Classification
  • 5 Mathematics of computing → Discrete mathematics
  • 4 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Computational complexity and cryptography
  • 3 Theory of computation → Solution concepts in game theory
  • 2 Applied computing → E-learning
  • Show More...

  • Refine by Keyword
  • 6 kernelization
  • 4 lower bounds
  • 4 parameterized complexity
  • 3 Markov chains
  • 3 Streaming Algorithms
  • Show More...

  • Refine by Type
  • 150 document

  • Refine by Publication Year
  • 18 2005
  • 18 2020
  • 16 2013
  • 13 2012
  • 12 2010
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact