@inproceedings{11827, abstract = {We study the metric facility location problem with client insertions and deletions. This setting differs from the classic dynamic facility location problem, where the set of clients remains the same, but the metric space can change over time. We show a deterministic algorithm that maintains a constant factor approximation to the optimal solution in worst-case time O~(2^{O(kappa^2)}) per client insertion or deletion in metric spaces while answering queries about the cost in O(1) time, where kappa denotes the doubling dimension of the metric. For metric spaces with bounded doubling dimension, the update time is polylogarithmic in the parameters of the problem.}, author = {Goranci, Gramoz and Henzinger, Monika H and Leniowski, Dariusz}, booktitle = {26th Annual European Symposium on Algorithms}, isbn = {9783959770811}, issn = {1868-8969}, location = {Helsinki, Finland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{A tree structure for dynamic facility location}}, doi = {10.4230/LIPICS.ESA.2018.39}, volume = {112}, year = {2018}, } @article{11768, abstract = {In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+ϵ)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary. In contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12] in the PRAM literature. An (h, ϵ)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated by their h-hop distance (given by a path containing at most h edges) on G′=(V, E ∪ F). Our algorithm can maintain an (no(1), ϵ)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest.}, author = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon}, issn = {1557-735X}, journal = {Journal of the ACM}, number = {6}, pages = {1--40}, publisher = {Association for Computing Machinery}, title = {{Decremental single-source shortest paths on undirected graphs in near-linear total update time}}, doi = {10.1145/3218657}, volume = {65}, year = {2018}, } @inproceedings{11872, abstract = {We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (Δ + 1)- vertex coloring and (2Δ – 1)-edge coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a (Δ + 1)-vertex coloring with O(log Δ) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o(1)Δ-vertex coloring with O(polylog Δ) amortized update time. (3) We present a simple, deterministic algorithm which maintains a (2Δ – 1)-edge coloring with O(log Δ) worst-case update time. This improves the recent O(Δ)-edge coloring algorithm with worst-case update time [4].}, author = {Bhattacharya, Sayan and Chakrabarty, Deeparnab and Henzinger, Monika H and Nanongkai, Danupon}, booktitle = {29th Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {New Orleans, LA, United States}, pages = {1 -- 20}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Dynamic algorithms for graph coloring}}, doi = {10.1137/1.9781611975031.1}, year = {2018}, } @inproceedings{11882, abstract = {The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability.}, author = {Henzinger, Monika H and Noe, Alexander and Schulz, Christian and Strash, Darren}, booktitle = {20th Workshop on Algorithm Engineering and Experiments}, location = {New Orleans, LA, United States}, pages = {48--61}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Practical minimum cut algorithms}}, doi = {10.1137/1.9781611975055.5}, year = {2018}, } @article{11890, abstract = {We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph 𝐺=(𝑉,𝐸), with |𝑉|=𝑛 and |𝐸|=𝑚, in 𝑜(𝑚‾‾√) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+𝜖) approximation in 𝑂(log𝑛/𝜖2) amortized time per update. For maximum matching, we show how to maintain a (3+𝜖) approximation in 𝑂(min(𝑛√/𝜖,𝑚1/3/𝜖2) amortized time per update and a (4+𝜖) approximation in 𝑂(𝑚1/3/𝜖2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457--464].}, author = {Bhattacharya, Sayan and Henzinger, Monika H and Italiano, Giuseppe F.}, issn = {1095-7111}, journal = {SIAM Journal on Computing}, number = {3}, pages = {859--887}, publisher = {Society for Industrial & Applied Mathematics}, title = {{Deterministic fully dynamic data structures for vertex cover and matching}}, doi = {10.1137/140998925}, volume = {47}, year = {2018}, } @inproceedings{11911, abstract = {It is common knowledge that there is no single best strategy for graph clustering, which justifies a plethora of existing approaches. In this paper, we present a general memetic algorithm, VieClus, to tackle the graph clustering problem. This algorithm can be adapted to optimize different objective functions. A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high-quality solutions in a short amount of time. We instantiate our scheme with local search for modularity and show that our algorithm successfully improves or reproduces all entries of the 10th DIMACS implementation challenge under consideration using a small amount of time.}, author = {Biedermann, Sonja and Henzinger, Monika H and Schulz, Christian and Schuster, Bernhard}, booktitle = {17th International Symposium on Experimental Algorithms}, isbn = {9783959770705}, issn = {1868-8969}, location = {L'Aquila, Italy}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Memetic graph clustering}}, doi = {10.4230/LIPICS.SEA.2018.3}, volume = {103}, year = {2018}, } @article{11958, abstract = {Solid reagents, leaching catalysts, and heterogeneous photocatalysts are commonly employed in batch processes but are ill-suited for continuous-flow chemistry. Heterogeneous catalysts for thermal reactions are typically used in packed-bed reactors, which cannot be penetrated by light and thus are not suitable for photocatalytic reactions involving solids. We demonstrate that serial micro-batch reactors (SMBRs) allow for the continuous utilization of solid materials together with liquids and gases in flow. This technology was utilized to develop selective and efficient fluorination reactions using a modified graphitic carbon nitride heterogeneous catalyst instead of costly homogeneous metal polypyridyl complexes. The merger of this inexpensive, recyclable catalyst and the SMBR approach enables sustainable and scalable photocatalysis.}, author = {Pieber, Bartholomäus and Shalom, Menny and Antonietti, Markus and Seeberger, Peter H. and Gilmore, Kerry}, issn = { 1521-3773}, journal = {Angewandte Chemie International Edition}, number = {31}, pages = {9976--9979}, publisher = {Wiley}, title = {{Continuous heterogeneous photocatalysis in serial micro-batch reactors}}, doi = {10.1002/anie.201712568}, volume = {57}, year = {2018}, } @article{1215, abstract = {Two generalizations of Itô formula to infinite-dimensional spaces are given. The first one, in Hilbert spaces, extends the classical one by taking advantage of cancellations when they occur in examples and it is applied to the case of a group generator. The second one, based on the previous one and a limit procedure, is an Itô formula in a special class of Banach spaces having a product structure with the noise in a Hilbert component; again the key point is the extension due to a cancellation. This extension to Banach spaces and in particular the specific cancellation are motivated by path-dependent Itô calculus.}, author = {Flandoli, Franco and Russo, Francesco and Zanco, Giovanni A}, journal = {Journal of Theoretical Probability}, number = {2}, pages = {789--826}, publisher = {Springer}, title = {{Infinite-dimensional calculus under weak spatial regularity of the processes}}, doi = {10.1007/s10959-016-0724-2}, volume = {31}, year = {2018}, } @article{124, abstract = {By investigating the in situ chemical and O-isotope compositions of olivine in lightly sintered dust agglomerates from the early Solar System, we constrain their origins and the retention of dust in the protoplanetary disk. The grain sizes of silicates in these agglomeratic olivine (AO) chondrules indicate that the grain sizes of chondrule precursors in the Renazzo-like carbonaceous (CR) chondrites ranged from <1 to 80 µm. We infer this grain size range to be equivalent to the size range for dust in the early Solar System. AO chondrules may contain, but are not solely composed of, recycled fragments of earlier formed chondrules. They also contain 16O-rich olivine related to amoeboid olivine aggregates and represent the best record of chondrule-precursor materials. AO chondrules contain one or more large grains, sometimes similar to FeO-poor (type I) and/or FeO-rich (type II) chondrules, while others contain a type II chondrule core. These morphologies are consistent with particle agglomeration by electrostatic charging of grains during collision, a process that may explain solid agglomeration in the protoplanetary disk in the micrometer size regime. The petrographic, isotopic, and chemical compositions of AO chondrules are consistent with chondrule formation by large-scale shocks, bow shocks, and current sheets. The petrographic, isotopic, and chemical similarities between AO chondrules in CR chondrites and chondrule-like objects from comet 81P/Wild 2 indicate that comets contain AO chondrules. We infer that these AO chondrules likely formed in the inner Solar System and migrated to the comet forming region at least 3 Ma after the formation of the first Solar System solids. Observations made in this study imply that the protoplanetary disk retained a dusty disk at least ∼3.7 Ma after the formation of the first Solar System solids, longer than half of the dusty accretion disks observed around other stars.}, author = {Waitukaitis, Scott R and Schrader, Devin and Nagashima, Kazuhide and Davidson, Jemma and Mccoy, Timothy and Conolly Jr, Harold and Lauretta, Dante}, journal = {Geochimica et Cosmochimica Acta}, pages = {405 -- 421}, publisher = {Elsevier}, title = {{The retention of dust in protoplanetary disks: evidence from agglomeration olivine chondrules from the outer solar system}}, doi = {10.1016/j.gca.2017.12.014}, volume = {223}, year = {2018}, } @article{125, abstract = {Many fields of study, including medical imaging, granular physics, colloidal physics, and active matter, require the precise identification and tracking of particle-like objects in images. While many algorithms exist to track particles in diffuse conditions, these often perform poorly when particles are densely packed together—as in, for example, solid-like systems of granular materials. Incorrect particle identification can have significant effects on the calculation of physical quantities, which makes the development of more precise and faster tracking algorithms a worthwhile endeavor. In this work, we present a new tracking algorithm to identify particles in dense systems that is both highly accurate and fast. We demonstrate the efficacy of our approach by analyzing images of dense, solid-state granular media, where we achieve an identification error of 5% in the worst evaluated cases. Going further, we propose a parallelization strategy for our algorithm using a GPU, which results in a speedup of up to 10× when compared to a sequential CPU implementation in C and up to 40× when compared to the reference MATLAB library widely used for particle tracking. Our results extend the capabilities of state-of-the-art particle tracking methods by allowing fast, high-fidelity detection in dense media at high resolutions.}, author = {Cerda, Mauricio and Waitukaitis, Scott R and Navarro, Cristóbal and Silva, Juan and Mujica, Nicolás and Hitschfeld, Nancy}, journal = {Computer Physics Communications}, pages = {8 -- 16}, publisher = {Elsevier}, title = {{A high-speed tracking algorithm for dense granular media}}, doi = {10.1016/j.cpc.2018.02.010}, volume = {227}, year = {2018}, } @article{126, abstract = {The Leidenfrost effect occurs when a liquid or stiff sublimable solid near a hot surface creates enough vapor beneath it to lift itself up and float. In contrast, vaporizable soft solids, e.g., hydrogels, have been shown to exhibit persistent bouncing - the elastic Leidenfrost effect. By carefully lowering hydrogel spheres towards a hot surface, we discover that they are also capable of floating. The bounce-to-float transition is controlled by the approach velocity and temperature, analogously to the "dynamic Leidenfrost effect." For the floating regime, we measure power-law scalings for the gap geometry, which we explain with a model that couples the vaporization rate to the spherical shape. Our results reveal that hydrogels are a promising pathway for controlling floating Leidenfrost objects through shape.}, author = {Waitukaitis, Scott R and Harth, Kirsten and Van Hecke, Martin}, journal = {Physical Review Letters}, number = {4}, publisher = {American Physical Society}, title = {{From bouncing to floating: the Leidenfrost effect with hydrogel spheres}}, doi = {10.1103/PhysRevLett.121.048001}, volume = {121}, year = {2018}, } @article{127, abstract = {The ideas of topology are breaking ground in origami-based metamaterials. Experiments now show that certain shapes — doughnuts included — exhibit topological bistability, and can be made to click between different topologically stable states.}, author = {Waitukaitis, Scott R}, journal = {Nature Physics}, number = {8}, pages = {777 -- 778}, publisher = {Nature Publishing Group}, title = {{Clicks for doughnuts}}, doi = {10.1038/s41567-018-0160-6}, volume = {14}, year = {2018}, } @inproceedings{174, abstract = {We survey recent efforts to quantify failures of the Hasse principle in families of rationally connected varieties.}, author = {Browning, Timothy D}, location = {Salt Lake City, Utah, USA}, number = {2}, pages = {89 -- 102}, publisher = {American Mathematical Society}, title = {{How often does the Hasse principle hold?}}, doi = {10.1090/pspum/097.2/01700}, volume = {97}, year = {2018}, } @article{176, abstract = {For a general class of non-negative functions defined on integral ideals of number fields, upper bounds are established for their average over the values of certain principal ideals that are associated to irreducible binary forms with integer coefficients.}, author = {Browning, Timothy D and Sofos, Efthymios}, journal = {International Journal of Nuber Theory}, number = {3}, pages = {547--567}, publisher = {World Scientific Publishing}, title = {{Averages of arithmetic functions over principal ideals}}, doi = {10.1142/S1793042119500283}, volume = {15}, year = {2018}, } @article{178, abstract = {We give an upper bound for the number of rational points of height at most B, lying on a surface defined by a quadratic form Q. The bound shows an explicit dependence on Q. It is optimal with respect to B, and is also optimal for typical forms Q.}, author = {Browning, Timothy D and Heath-Brown, Roger}, issn = {2397-3129}, journal = {Discrete Analysis}, pages = {1 -- 29}, publisher = {Alliance of Diamond Open Access Journals}, title = {{Counting rational points on quadric surfaces}}, doi = {10.19086/da.4375}, volume = {15}, year = {2018}, } @inproceedings{185, abstract = {We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once.}, author = {Fulek, Radoslav and Kynčl, Jan}, isbn = {978-3-95977-066-8}, location = {Budapest, Hungary}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Hanani-Tutte for approximating maps of graphs}}, doi = {10.4230/LIPIcs.SoCG.2018.39}, volume = {99}, year = {2018}, } @inproceedings{188, abstract = {Smallest enclosing spheres of finite point sets are central to methods in topological data analysis. Focusing on Bregman divergences to measure dissimilarity, we prove bounds on the location of the center of a smallest enclosing sphere. These bounds depend on the range of radii for which Bregman balls are convex.}, author = {Edelsbrunner, Herbert and Virk, Ziga and Wagner, Hubert}, location = {Budapest, Hungary}, pages = {35:1 -- 35:13}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Smallest enclosing spheres and Chernoff points in Bregman geometry}}, doi = {10.4230/LIPIcs.SoCG.2018.35}, volume = {99}, year = {2018}, } @article{2015, abstract = {We consider the problem of learning a Bayesian network or directed acyclic graph model from observational data. A number of constraint‐based, score‐based and hybrid algorithms have been developed for this purpose. Statistical consistency guarantees of these algorithms rely on the faithfulness assumption, which has been shown to be restrictive especially for graphs with cycles in the skeleton. We here propose the sparsest permutation (SP) algorithm, showing that learning Bayesian networks is possible under strictly weaker assumptions than faithfulness. This comes at a computational price, thereby indicating a statistical‐computational trade‐off for causal inference algorithms. In the Gaussian noiseless setting, we prove that the SP algorithm boils down to finding the permutation of the variables with the sparsest Cholesky decomposition of the inverse covariance matrix, which is equivalent to ℓ0‐penalized maximum likelihood estimation. We end with a simulation study showing that in line with the proven stronger consistency guarantees, and the SP algorithm compares favourably to standard causal inference algorithms in terms of accuracy for a given sample size.}, author = {Raskutti, Garvesh and Uhler, Caroline}, journal = {STAT}, number = {1}, publisher = {Wiley}, title = {{Learning directed acyclic graphs based on sparsest permutations}}, doi = {10.1002/sta4.183}, volume = {7}, year = {2018}, } @article{306, abstract = {A cornerstone of statistical inference, the maximum entropy framework is being increasingly applied to construct descriptive and predictive models of biological systems, especially complex biological networks, from large experimental data sets. Both its broad applicability and the success it obtained in different contexts hinge upon its conceptual simplicity and mathematical soundness. Here we try to concisely review the basic elements of the maximum entropy principle, starting from the notion of ‘entropy’, and describe its usefulness for the analysis of biological systems. As examples, we focus specifically on the problem of reconstructing gene interaction networks from expression data and on recent work attempting to expand our system-level understanding of bacterial metabolism. Finally, we highlight some extensions and potential limitations of the maximum entropy approach, and point to more recent developments that are likely to play a key role in the upcoming challenges of extracting structures and information from increasingly rich, high-throughput biological data.}, author = {De Martino, Andrea and De Martino, Daniele}, journal = {Heliyon}, number = {4}, publisher = {Elsevier}, title = {{An introduction to the maximum entropy approach and its application to inference problems in biology}}, doi = {10.1016/j.heliyon.2018.e00596}, volume = {4}, year = {2018}, } @book{3300, abstract = {This book first explores the origins of this idea, grounded in theoretical work on temporal logic and automata. The editors and authors are among the world's leading researchers in this domain, and they contributed 32 chapters representing a thorough view of the development and application of the technique. Topics covered include binary decision diagrams, symbolic model checking, satisfiability modulo theories, partial-order reduction, abstraction, interpolation, concurrency, security protocols, games, probabilistic model checking, and process algebra, and chapters on the transfer of theory to industrial practice, property specification languages for hardware, and verification of real-time systems and hybrid systems. The book will be valuable for researchers and graduate students engaged with the development of formal methods and verification tools.}, author = {Clarke, Edmund M. and Henzinger, Thomas A and Veith, Helmut and Bloem, Roderick}, isbn = {978-3-319-10574-1}, pages = {XLVIII, 1212}, publisher = {Springer Nature}, title = {{Handbook of Model Checking}}, doi = {10.1007/978-3-319-10575-8}, year = {2018}, }