@inproceedings{20159,
abstract = {Let G = (V,E) be an undirected graph on n vertices with non-negative capacities on its edges. The mincut sensitivity problem for the insertion of an edge is defined as follows. Build a compact data structure for G and a given set S ⊆ V of vertices that, on receiving any edge (x,y) ∈ S×S of positive capacity as query input, can efficiently report the set of all pairs from S× S whose mincut value increases upon insertion of the edge (x,y) to G. The only result that exists for this problem is for a single pair of vertices (Picard and Queyranne, Mathematical Programming Study, 13 (1980), 8-16). We present the following results for the single source and the all-pairs versions of this problem.
1) Single source: Given any designated source vertex s, there exists a data structure of size 𝒪(|S|) that can output all those vertices from S whose mincut value to s increases upon insertion of any given edge. The time taken by the data structure to answer any query is 𝒪(|S|).
2) All-pairs: There exists an 𝒪(|S|²) size data structure that can output all those pairs of vertices from S× S whose mincut value gets increased upon insertion of any given edge. The time taken by the data structure to answer any query is 𝒪(k), where k is the number of pairs of vertices whose mincut increases.
For both these versions, we also address the problem of reporting the values of the mincuts upon insertion of any given edge. To derive our results, we use interesting insights into the nearest and the farthest mincuts for a pair of vertices. In addition, a crucial result, that we establish and use in our data structures, is that there exists a directed acyclic graph of 𝒪(n) size that compactly stores the farthest mincuts from all vertices of V to a designated vertex s in the graph. We believe that this result is of independent interest, especially, because it also complements a previously existing result by Hariharan et al. (STOC 2007) that the nearest mincuts from all vertices of V to s is a laminar family, and hence, can be stored compactly in a tree of 𝒪(n) size.},
author = {Baswana, Surender and Gupta, Shiv and Knollmann, Till},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
isbn = {978-3-95977-162-7},
issn = {1868-8969},
keyword = {Mincut, Sensitivity, Data Structure},
pages = {12:1--12:14},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
title = {{Mincut Sensitivity Data Structures for the Insertion of an Edge}},
doi = {10.4230/LIPIcs.ESA.2020.12},
volume = {173},
year = {2020},
}
@inproceedings{18022,
author = {Augstein, Mirjam and Buschek, Daniel and Herder, Eelco and Loepp, Benedikt and Yigitbas, Enes and Ziegler, Jürgen},
booktitle = {Proceedings of the Mensch und Computer 2020 (MuC ’20)},
publisher = {ACM},
title = {{UCAI 2020 - 1st International Workshop on User-Centered Artificial Intelligence}},
year = {2020},
}
@article{17086,
author = {Gries, T. and Redlin, M.},
issn = {1612-4804},
journal = {International Economics and Economic Policy},
pages = {923--944},
title = {{Trade and economic development: global causality and development- and openness-related heterogeneity}},
doi = {10.1007/s10368-020-00467-1},
volume = {17},
year = {2020},
}
@inproceedings{16968,
abstract = {In this work, we initiate the research about the Gathering problem for robots
with limited viewing range in the three-dimensional Euclidean space. In the
Gathering problem, a set of initially scattered robots is required to gather at
the same position. The robots' capabilities are very restricted -- they do not
agree on any coordinate system or compass, have a limited viewing range, have
no memory of the past and cannot communicate. We study the problem in two
different time models, in FSYNC (fully synchronized discrete rounds) and the
continuous time model. For FSYNC, we introduce the 3D-Go-To-The-Center-strategy
and prove a runtime of $\Theta(n^2)$ that matches the currently best runtime
bound for the same model in the Euclidean plane [SPAA'11]. Our main result is
the generalization of contracting strategies (continuous time) from
[Algosensors'17] to three dimensions. In contracting strategies, every robot
that is located on the global convex hull of all robots' positions moves with
full speed towards the inside of the convex hull. We prove a runtime bound of
$O(\Delta \cdot n^{3/2})$ for any three-dimensional contracting strategy, where
$\Delta$ denotes the diameter of the initial configuration. This comes up to a
factor of $\sqrt{n}$ close to the lower bound of $\Omega (\Delta \cdot n)$
which is already true in two dimensions. In general, it might be hard for
robots with limited viewing range to decide whether they are located on the
global convex hull and which movement maintains the connectivity of the swarm,
rendering the design of concrete contracting strategies a challenging task. We
prove that the continuous variant of 3D-Go-To-The-Center is contracting and
keeps the swarm connected. Moreover, we give a simple design criterion for
three-dimensional contracting strategies that maintains the connectivity of the
swarm and introduce an exemplary strategy based on this criterion.},
author = {Braun, Michael and Castenow, Jannik and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO)},
location = {Paderborn},
publisher = {Springer},
title = {{Local Gathering of Mobile Robots in Three Dimensions}},
doi = {10.1007/978-3-030-54921-3_4},
year = {2020},
}
@inproceedings{20274,
author = {Bila, Eleni and Doherty, Simon and Dongol, Brijesh and Derrick, John and Schellhorn, Gerhard and Wehrheim, Heike},
booktitle = {Formal Techniques for Distributed Objects, Components, and Systems - 40th {IFIP} {WG} 6.1 International Conference, {FORTE} 2020, Held as Part of the 15th International Federated Conference on Distributed Computing Techniques, DisCoTec 2020, Valletta, Malta, June 15-19, 2020, Proceedings},
editor = {Gotsman, Alexey and Sokolova, Ana},
pages = {39--58},
publisher = {Springer},
title = {{Defining and Verifying Durable Opacity: Correctness for Persistent Software Transactional Memory}},
doi = {10.1007/978-3-030-50086-3\_3},
volume = {12136},
year = {2020},
}
@article{20279,
author = {Sharma, Arnab and Wehrheim, Heike},
journal = {CoRR},
title = {{Testing Monotonicity of Machine Learning Models}},
volume = {abs/2002.12278},
year = {2020},
}
@inproceedings{20301,
author = {Günter, Heinrich and Meschut, Gerson},
booktitle = {73rd IIW Annual Assembly and International Conference},
title = {{Joining of high-strength steel grades in lightweight structures using single-stage resistance element welding on conventional resistance spot welding machines}},
year = {2020},
}
@inproceedings{20306,
author = {Tornede, Alexander and Wever, Marcel Dominik and Hüllermeier, Eyke},
booktitle = {Workshop MetaLearn 2020 @ NeurIPS 2020},
location = {Online},
title = {{Towards Meta-Algorithm Selection}},
year = {2020},
}
@book{20318,
author = {Göddecke, Johannes and Meschut, Gerson and Gude, Maik and Lieberwirth, Holger and Tekkaya, Erman and Zaeh, Michael and Stegelmann, Michael and Müller, Michael and Böhme, Kurt and Krampitz, Thomas and Zöllner, Mareen and Hahn, Marlon and Schmitz, Fabian and Hofer, Andreas and Grohmann, Sandra},
isbn = {978-3867806435},
pages = {82},
publisher = {Plattform FOREL},
title = {{FOREL-Wegweiser: Handlungsempfehlungen für den ressourceneffizienten Leichtbau }},
year = {2020},
}
@inproceedings{16898,
abstract = {Electronic structure calculations based on density-functional theory (DFT)
represent a significant part of today's HPC workloads and pose high demands on
high-performance computing resources. To perform these quantum-mechanical DFT
calculations on complex large-scale systems, so-called linear scaling methods
instead of conventional cubic scaling methods are required. In this work, we
take up the idea of the submatrix method and apply it to the DFT computations
in the software package CP2K. For that purpose, we transform the underlying
numeric operations on distributed, large, sparse matrices into computations on
local, much smaller and nearly dense matrices. This allows us to exploit the
full floating-point performance of modern CPUs and to make use of dedicated
accelerator hardware, where performance has been limited by memory bandwidth
before. We demonstrate both functionality and performance of our implementation
and show how it can be accelerated with GPUs and FPGAs.},
author = {Lass, Michael and Schade, Robert and Kühne, Thomas and Plessl, Christian},
booktitle = {Proc. International Conference for High Performance Computing, Networking, Storage and Analysis (SC)},
location = {Atlanta, GA, US},
pages = {1127--1140},
publisher = {IEEE Computer Society},
title = {{A Submatrix-Based Method for Approximate Matrix Function Evaluation in the Quantum Chemistry Code CP2K}},
doi = {10.1109/SC41405.2020.00084},
year = {2020},
}