A Framework for Algorithm Stability and Its Application to Kinetic Euclidean MSTs
Wouter Meulemans, Bettina Speckmann, Kevin Verbeek, and Jules Wulms. LATIN 2018: Theoretical Informatics,
pp. 805—819,
2018.
<p>We say that an algorithm is stable if small changes in the input result in small changes in the output. This kind of algorithm stability is particularly relevant when analyzing and visualizing time-varying data. Stability in general plays an important role in a wide variety of areas, such as numerical analysis, machine learning, and topology, but is poorly understood in the context of (combinatorial) algorithms. In this paper we present a framework for analyzing the stability of algorithms. We focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes. Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability. We demonstrate the use of our stability framework by applying it to kinetic Euclidean minimum spanning trees.</p>
@article{a-framework-for-algorithm-stability-and-its-application-to-kinetic-euclidean-msts:2018, title = {A Framework for Algorithm Stability and Its Application to Kinetic Euclidean MSTs}, author = {Wouter Meulemans and Bettina Speckmann and Kevin Verbeek and Jules Wulms}, year = {2018}, bookTitle = {LATIN 2018: Theoretical Informatics},}
The Painter’s Problem
A.I. van Goethem, I. Kostitsyna, M.J. van Kreveld, W. Meulemans, M.F.M. Sondag, and J.J.H.M. Wulms. 25th International Symposium on Graph Drawing and Network Visualization (GD),
10692 LNCS:492—505,
2018.
<p>Motivated by a new way of visualizing hypergraphs, we study the following problem. Consider a rectangular grid and a set of colors X Each cell s in the grid is assigned a subset of colors X<sub>s</sub> ⊆ X and should be partitioned such that for each color c ∈ X<sub>s</sub> at least one piece in the cell is identified with c. Cells assigned the empty color set remain white. We focus on the case where X = {red, blue}. Is it possible to partition each cell in the grid such that the unions of the resulting red and blue pieces form two connected polygons? We analyze the combinatorial properties and derive a necessary and sufficient condition for such a painting. We show that if a painting exists, there exists a painting with bounded complexity per cell. This painting has at most five colored pieces per cell if the grid contains white cells, and at most two colored pieces per cell if it does not.</p>
@article{the-painter-s-problem:2018, title = {The Painter’s Problem}, author = {A.I. van Goethem and I. Kostitsyna and M.J. van Kreveld and W. Meulemans and M.F.M. Sondag and J.J.H.M. Wulms}, year = {2018}, bookTitle = {25th International Symposium on Graph Drawing and Network Visualization (GD)},}
A Framework for Algorithm Stability and Its Application to Kinetic Euclidean MSTs
W. Meulemans, B. Speckmann, K.A.B. Verbeek, and J.J.H.M. Wulms. Proceedings of the 34th European Workshop on Computational Geometry (EuroCG),
pp. 11:1—11:6,
2018.
We say that an algorithm is stable if small changes in the input result in small changes in the output. This kind of algorithm stability is particularly relevant when analyzing and visualizing time-varying data. Stability in general plays an important role in a wide variety of areas, such as numerical analysis, machine learning, and topology, but is poorly understood in the context of (combinatorial) algorithms. <br/><br/>In this paper we present a framework for analyzing the stability of algorithms. We focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes. <br/>Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability. <br/>We demonstrate the use of topological stability by applying it to kinetic Euclidean minimum spanning trees.
@article{a-framework-for-algorithm-stability-and-its-application-to-kinetic-euclidean-msts:2018, title = {A Framework for Algorithm Stability and Its Application to Kinetic Euclidean MSTs}, author = {W. Meulemans and B. Speckmann and K.A.B. Verbeek and J.J.H.M. Wulms}, year = {2018}, bookTitle = {Proceedings of the 34th European Workshop on Computational Geometry (EuroCG)},}
The Hardness of Witness Puzzles
I. Kostitsyna, Maarten Löffler, M.F.M. Sondag, W.M. Sonke, and J.J.H.M. Wulms. Proc. 34th European Workshop on Computational Geometry (EuroCG),
pp. 67:1—67:6,
2018.
@article{the-hardness-of-witness-puzzles:2018, title = {The Hardness of Witness Puzzles}, author = {I. Kostitsyna and Maarten Löffler and M.F.M. Sondag and W.M. Sonke and J.J.H.M. Wulms}, year = {2018}, bookTitle = {Proc. 34th European Workshop on Computational Geometry (EuroCG)},}
We say that an algorithm is stable if small changes in the input result in small changes in the output. Algorithm stability plays an important role when analyzing and visualizing time-varying data. However, so far, there are only few theoretical results on the stability of algorithms, possibly due to a lack of theoretical analysis tools. In this paper we present a framework for analyzing the stability of algorithms. We focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes. Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability. We demonstrate the use of our stability framework by applying it to kinetic Euclidean minimum spanning trees.
@article{a-framework-for-algorithm-stability:2017, title = {A Framework for Algorithm Stability}, author = {W. Meulemans and B. Speckmann and K.A.B. Verbeek and J. Wulms}, year = {2017}, bookTitle = {arXiv},}
The Painter's Problem: Covering a Grid with Colored Connected Polygons
A.I. van Goethem, I. Kostitsyna, M. van Kreveld, W. Meulemans, M.F.M. Sondag, and J.J.H.M. Wulms. arXiv,
2017.
Motivated by a new way of visualizing hypergraphs, we study the following problem. Consider a rectangular grid and a set of colors χ. Each cell s in the grid is assigned a subset of colors χs⊆χ and should be partitioned such that for each color c∈χs at least one piece in the cell is identified with c. Cells assigned the empty color set remain white. We focus on the case where χ={red,blue}. Is it possible to partition each cell in the grid such that the unions of the resulting red and blue pieces form two connected polygons? We analyze the combinatorial properties and derive a necessary and sufficient condition for such a painting. We show that if a painting exists, there exists a painting with bounded complexity per cell. This painting has at most five colored pieces per cell if the grid contains white cells, and at most two colored pieces per cell if it does not.
@article{the-painter-s-problem-covering-a-grid-with-colored-connected-polygons:2017, title = {The Painter's Problem: Covering a Grid with Colored Connected Polygons}, author = {A.I. van Goethem and I. Kostitsyna and M. van Kreveld and W. Meulemans and M.F.M. Sondag and J.J.H.M. Wulms}, year = {2017}, bookTitle = {arXiv},}
Lower Bounds for Protrusion Replacement by Counting Equivalence Classes
B.M.P. Jansen and J.J.H.M. Wulms. 11th International Symposium on Parameterized and Exact Computation (IPEC 2016),
pp. 1—12,
2017.
Garnero et al. [SIAM J. Discrete Math. 2015, 29(4):1864-1894] recently introduced a framework based on dynamic programming to make applications of the protrusion replacement technique constructive and to obtain explicit upper bounds on the involved constants. They show that for several graph problems, for every boundary size t one can find an explicit set R_t of representatives. Any subgraph H with a boundary of size t can be replaced with a representative H' in R_t such that the effect of this replacement on the optimum can be deduced from H and H' alone. Their upper bounds on the size of the graphs in R_t grow triple-exponentially with t. In this paper we complement their results by lower bounds on the sizes of representatives, in terms of the boundary size t. For example, we show that each set of planar representatives R_t for the Independent Set problem contains a graph with Omega(2^t / sqrt{4t}) vertices. This lower bound even holds for sets that only represent the planar subgraphs of bounded pathwidth. To obtain our results we provide a lower bound on the number of equivalence classes of the canonical equivalence relation for Independent Set on t-boundaried graphs. We also find an elegant characterization of the number of equivalence classes in general graphs, in terms of the number of monotone functions of a certain kind. Our results show that the number of equivalence classes is at most 2^{2^t}, improving on earlier bounds of the form (t+1)^{2^t}.
@article{lower-bounds-for-protrusion-replacement-by-counting-equivalence-classes:2017, title = {Lower Bounds for Protrusion Replacement by Counting Equivalence Classes}, author = {B.M.P. Jansen and J.J.H.M. Wulms}, year = {2017}, bookTitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},}
Garnero et al. [SIAM J. Discrete Math. 2015, 29(4):1864--1894] recently introduced a framework based on dynamic programming to make applications of the protrusion replacement technique constructive and to obtain explicit upper bounds on the involved constants. They show that for several graph problems, for every boundary size $t$ one can find an explicit set $\mathcal{R}_t$ of representatives. Any subgraph $H$ with a boundary of size $t$ can be replaced with a representative $H' \in \mathcal{R}_t$ such that the effect of this replacement on the optimum can be deduced from $H$ and $H'$ alone. Their upper bounds on the size of the graphs in $\mathcal{R}_t$ grow triple-exponentially with $t$. In this paper we complement their results by lower bounds on the sizes of representatives, in terms of the boundary size $t$. For example, we show that each set of planar representatives $\mathcal{R}_t$ for Independent Set or Dominating Set contains a graph with $\Omega(2^t / \sqrt{4t})$ vertices. This lower bound even holds for sets that only represent the planar subgraphs of bounded pathwidth. To obtain our results we provide a lower bound on the number of equivalence classes of the canonical equivalence relation for Independent Set on $t$-boundaried graphs. We also find an elegant characterization of the number of equivalence classes in general graphs, in terms of the number of monotone functions of a certain kind. Our results show that the number of equivalence classes is at most $2^{2^t}$, improving on earlier bounds of the form $(t+1)^{2^t}$.
@article{lower-bounds-for-protrusion-replacement-by-counting-equivalence-classes:2016, title = {Lower Bounds for Protrusion Replacement by Counting Equivalence Classes}, author = {B.M.P. Jansen and J.J.H.M. Wulms}, year = {2016}, bookTitle = {arXiv},}
Geo Word Clouds
K.A. Buchin, D.J.A. Creemers, A. Lazzarotto , B. Speckmann, and J.J.H.M. Wulms. 2016 IEEE Pacific Visualization Symposium (PacificVis), 19-22 April 2016, Taipei, Taiwan ,
pp. 144—151,
2016.
Word clouds are a popular method to visualize the frequency of words in textual data. Nowadays many text-based data sets, such as Flickr tags, are geo-referenced, that is, they have an important spatial component. However, existing automated methods to generate word clouds are unable to incorporate such spatial information. We introduce geo word clouds: word clouds which capture not only the frequency but also the spatial relevance of words. Our input is a set of locations from one (or more) geographic regions with (possibly several) text labels per location. We aggregate word frequencies according to point clusters and employ a greedy strategy to place appropriately sized labels without overlap as close as possible to their corresponding locations. While doing so we "draw" the spatial shapes of the geographic regions with the corresponding labels. We experimentally explore trade-offs concerning the location of labels, their relative sizes and the number of spatial clusters. The resulting word clouds are visually pleasing and have a low error in terms of relative scaling and locational accuracy of words, while using a small number of clusters per label.
@article{geo-word-clouds:2016, title = {Geo Word Clouds}, author = {K.A. Buchin and D.J.A. Creemers and A. Lazzarotto and B. Speckmann and J.J.H.M. Wulms}, year = {2016}, bookTitle = {2016 IEEE Pacific Visualization Symposium (PacificVis), 19-22 April 2016, Taipei, Taiwan },}
Continuous Integration in GITHUB: Experiences with TRAVIS-CI
B.N. Vasilescu, S.B. van Schuylenburg, Jules Wulms, A. Serebrenik, and M.G.J. Brand, van den. Benevol 2014 (Seminar on Software Evolution in Belgium and the Netherlands, Amsterdam, The Netherlands, November 27-28, 2014),
pp. 12—13,
2014.
@article{continuous-integration-in-github-experiences-with-travis-ci:2014, title = {Continuous Integration in GITHUB: Experiences with TRAVIS-CI}, author = {B.N. Vasilescu and S.B. van Schuylenburg and Jules Wulms and A. Serebrenik and M.G.J. Brand, van den}, year = {2014}, bookTitle = {Benevol 2014 (Seminar on Software Evolution in Belgium and the Netherlands, Amsterdam, The Netherlands, November 27-28, 2014)},}
Continuous Integration in a Social-Coding World: Empirical Evidence from GitHub
B.N. Vasilescu, S.B. van Schuylenburg, Jules Wulms, A. Serebrenik, and M.G.J. Brand, van den. 30th International Conference on Software Maintenance and Evolution (ICSME 2014), Victoria, BC, Canada, September 29-October 3, 2014,
pp. 401—405,
2014.
Continuous integration is a software engineering practice of frequently merging all developer working copies with a shared main branch, e.g., several times a day. With the advent of GitHub, a platform well known for its "social coding" features that aid collaboration and sharing, and currently the largest code host in the open source world, collaborative software development has never been more prominent. In GitHub development one can distinguish between two types of developer contributions to a project: direct ones, coming from a typically small group of developers with write access to the main project repository, and indirect ones, coming from developers who fork the main repository, update their copies locally, and submit pull requests for review and merger. In this paper we explore how GitHub developers use continuous integration as well as whether the contribution type (direct versus indirect) and different project characteristics (e.g., main programming language, or project age) are associated with the success of the automatic builds.
@article{continuous-integration-in-a-social-coding-world-empirical-evidence-from-github:2014, title = {Continuous Integration in a Social-Coding World: Empirical Evidence from GitHub}, author = {B.N. Vasilescu and S.B. van Schuylenburg and Jules Wulms and A. Serebrenik and M.G.J. Brand, van den}, year = {2014}, bookTitle = {30th International Conference on Software Maintenance and Evolution (ICSME 2014), Victoria, BC, Canada, September 29-October 3, 2014},}
Master's Thesis
Jules Wulms, Lower bounds for preprocessing algorithms based on protrusion replacement, TU Eindhoven, 2016, PDF