Showing 1–43 of 43 results for author: Klein, K

Physics-augmented neural networks for constitutive modeling of hyperelastic geometrically exact beams

Authors: Jasper O. Schommartz, Dominik K. Klein, Juan C. Alzate Cobo, Oliver Weeger

Abstract: We present neural network-based constitutive models for hyperelastic geometrically exact beams. The proposed models are physics-augmented, i.e., formulated to fulfill important mechanical conditions by construction. Strains and curvatures of the beam are used as input for feed-forward neural networks that represent the effective hyperelastic beam potential. Forces and moments are then received as… ▽ More We present neural network-based constitutive models for hyperelastic geometrically exact beams. The proposed models are physics-augmented, i.e., formulated to fulfill important mechanical conditions by construction. Strains and curvatures of the beam are used as input for feed-forward neural networks that represent the effective hyperelastic beam potential. Forces and moments are then received as the gradients of the beam potential, ensuring thermodynamic consistency. Furthermore, normalization conditions are considered via additional projection terms. To include the symmetry of beams with point-symmetric cross-sections, a flip symmetry constraint is introduced. Additionally, parameterized models are proposed that can represent the beam's constitutive behavior for varying cross-sectional geometries. The physically motivated parameterization takes into account the influence of the beam radius on the beam potential. Formulating the beam potential as a neural network provides a highly flexible model. This enables efficient constitutive surrogate modeling for geometrically exact beams with nonlinear material behavior and cross-sectional deformation, which otherwise would require computationally much more expensive methods. The models are calibrated to data generated for beams with circular, deformable cross-sections and varying radii, showing excellent accuracy and generalization. The applicability of the proposed model is further demonstrated by applying it in beam simulations. In all studied cases, the proposed model shows excellent performance. △ Less

Submitted 30 June, 2024; originally announced July 2024.

Wooly Graphs : A Mathematical Framework For Knitting

Authors: Kathryn Gray, Brian Bell, Diana Sieper, Stephen Kobourov, Falk Schreiber, Karsten Klein, Seokhee Hong

Abstract: This paper aims to develop a mathematical foundation to model knitting with graphs. We provide a precise definition for knit objects with a knot theoretic component and propose a simple undirected graph, a simple directed graph, and a directed multigraph model for any arbitrary knit object. Using these models, we propose natural categories related to the complexity of knitting structures. We use t… ▽ More This paper aims to develop a mathematical foundation to model knitting with graphs. We provide a precise definition for knit objects with a knot theoretic component and propose a simple undirected graph, a simple directed graph, and a directed multigraph model for any arbitrary knit object. Using these models, we propose natural categories related to the complexity of knitting structures. We use these categories to explore the hardness of determining whether a knit object of each class exists for a given graph. We show that while this problem is NP-hard in general, under specific cases, there are linear and polynomial time algorithms which take advantage of unique properties of common knitting techniques. This work aims to bridge the gap between textile arts and graph theory, offering a useful and rigorous framework for analyzing knitting objects using their corresponding graphs and for generating knitting objects from graphs. △ Less

Submitted 3 July, 2024; v1 submitted 29 June, 2024; originally announced July 2024.

Comments: 11 pages, 4 tables, 5 figures

CORE-BEHRT: A Carefully Optimized and Rigorously Evaluated BEHRT

Authors: Mikkel Odgaard, Kiril Vadimovic Klein, Sanne Møller Thysen, Espen Jimenez-Solem, Martin Sillesen, Mads Nielsen

Abstract: BERT-based models for Electronic Health Records (EHR) have surged in popularity following the release of BEHRT and Med-BERT. Subsequent models have largely built on these foundations despite the fundamental design choices of these pioneering models remaining underexplored. To address this issue, we introduce CORE-BEHRT, a Carefully Optimized and Rigorously Evaluated BEHRT. Through incremental opti… ▽ More BERT-based models for Electronic Health Records (EHR) have surged in popularity following the release of BEHRT and Med-BERT. Subsequent models have largely built on these foundations despite the fundamental design choices of these pioneering models remaining underexplored. To address this issue, we introduce CORE-BEHRT, a Carefully Optimized and Rigorously Evaluated BEHRT. Through incremental optimization, we isolate the sources of improvement for key design choices, giving us insights into the effect of data representation and individual technical components on performance. Evaluating this across a set of generic tasks (death, pain treatment, and general infection), we showed that improving data representation can increase the average downstream performance from 0.785 to 0.797 AUROC, primarily when including medication and timestamps. Improving the architecture and training protocol on top of this increased average downstream performance to 0.801 AUROC. We then demonstrated the consistency of our optimization through a rigorous evaluation across 25 diverse clinical prediction tasks. We observed significant performance increases in 17 out of 25 tasks and improvements in 24 tasks, highlighting the generalizability of our findings. Our findings provide a strong foundation for future work and aim to increase the trustworthiness of BERT-based EHR models. △ Less

Submitted 22 May, 2024; v1 submitted 23 April, 2024; originally announced April 2024.

Comments: 11 pages, 5 figures

CARISMA: CAR-Integrated Service Mesh Architecture

Authors: Kevin Klein, Pascal Hirmer, Steffen Becker

Abstract: The amount of software in modern cars is increasing continuously with traditional electric/electronic (E/E) architectures reaching their limit when deploying complex applications, e.g., regarding bandwidth or computational power. To mitigate this situation, more powerful computing platforms are being employed and applications are developed as distributed applications, e.g., involving microservices… ▽ More The amount of software in modern cars is increasing continuously with traditional electric/electronic (E/E) architectures reaching their limit when deploying complex applications, e.g., regarding bandwidth or computational power. To mitigate this situation, more powerful computing platforms are being employed and applications are developed as distributed applications, e.g., involving microservices. Microservices received widespread adoption and changed the way modern applications are developed. However, they also introduce additional complexity regarding inter-service communication. This has led to the emergence of service meshes, a promising approach to cope with this complexity. In this paper, we present an architecture applying the service mesh approach to automotive E/E platforms comprising multiple interlinked High-Performance Computers (HPCs). We validate the feasibility of our approach through a prototypical implementation. △ Less

Submitted 7 March, 2024; originally announced March 2024.

Tight Lower Bounds for Block-Structured Integer Programs

Authors: Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, Asaf Levin

Abstract: We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few constraints in a recursive pattern; and transposing their constraint matrix yields multi-stage IPs. The state-of-the-art algorithms to solve these IPs have an exponential gap in their running times, making it natural to… ▽ More We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few constraints in a recursive pattern; and transposing their constraint matrix yields multi-stage IPs. The state-of-the-art algorithms to solve these IPs have an exponential gap in their running times, making it natural to ask whether this gap is inherent. We answer this question affirmative. Assuming the Exponential Time Hypothesis, we prove lower bounds showing that the exponential difference is necessary, and that the known algorithms are near optimal. Moreover, we prove unconditional lower bounds on the norms of the Graver basis, a fundamental building block of all known algorithms to solve these IPs. This shows that none of the current approaches can be improved beyond this bound. △ Less

Submitted 27 February, 2024; originally announced February 2024.

Nonlinear electro-elastic finite element analysis with neural network constitutive models

Authors: Dominik K. Klein, Rogelio Ortigosa, Jesús Martínez-Frutos, Oliver Weeger

Abstract: In the present work, the applicability of physics-augmented neural network (PANN) constitutive models for complex electro-elastic finite element analysis is demonstrated. For the investigations, PANN models for electro-elastic material behavior at finite deformations are calibrated to different synthetically generated datasets, including an analytical isotropic potential, a homogenised rank-one la… ▽ More In the present work, the applicability of physics-augmented neural network (PANN) constitutive models for complex electro-elastic finite element analysis is demonstrated. For the investigations, PANN models for electro-elastic material behavior at finite deformations are calibrated to different synthetically generated datasets, including an analytical isotropic potential, a homogenised rank-one laminate, and a homogenised metamaterial with a spherical inclusion. Subsequently, boundary value problems inspired by engineering applications of composite electro-elastic materials are considered. Scenarios with large electrically induced deformations and instabilities are particularly challenging and thus necessitate extensive investigations of the PANN constitutive models in the context of finite element analyses. First of all, an excellent prediction quality of the model is required for very general load cases occurring in the simulation. Furthermore, simulation of large deformations and instabilities poses challenges on the stability of the numerical solver, which is closely related to the constitutive model. In all cases studied, the PANN models yield excellent prediction qualities and a stable numerical behavior even in highly nonlinear scenarios. This can be traced back to the PANN models excellent performance in learning both the first and second derivatives of the ground truth electro-elastic potentials, even though it is only calibrated on the first derivatives. Overall, this work demonstrates the applicability of PANN constitutive models for the efficient and robust simulation of engineering applications of composite electro-elastic materials. △ Less

Submitted 10 February, 2024; originally announced February 2024.

AutArch: An AI-assisted workflow for object detection and automated recording in archaeological catalogues

Authors: Kevin Klein, Alyssa Wohde, Alexander V. Gorelik, Volker Heyd, Ralf Lämmel, Yoan Diekmann, Maxime Brami

Abstract: The context of this paper is the creation of large uniform archaeological datasets from heterogeneous published resources, such as find catalogues - with the help of AI and Big Data. The paper is concerned with the challenge of consistent assemblages of archaeological data. We cannot simply combine existing records, as they differ in terms of quality and recording standards. Thus, records have to… ▽ More The context of this paper is the creation of large uniform archaeological datasets from heterogeneous published resources, such as find catalogues - with the help of AI and Big Data. The paper is concerned with the challenge of consistent assemblages of archaeological data. We cannot simply combine existing records, as they differ in terms of quality and recording standards. Thus, records have to be recreated from published archaeological illustrations. This is only a viable path with the help of automation. The contribution of this paper is a new workflow for collecting data from archaeological find catalogues available as legacy resources, such as archaeological drawings and photographs in large unsorted PDF files; the workflow relies on custom software (AutArch) supporting image processing, object detection, and interactive means of validating and adjusting automatically retrieved data. We integrate artificial intelligence (AI) in terms of neural networks for object detection and classification into the workflow, thereby speeding up, automating, and standardising data collection. Objects commonly found in archaeological catalogues - such as graves, skeletons, ceramics, ornaments, stone tools and maps - are detected. Those objects are spatially related and analysed to extract real-life attributes, such as the size and orientation of graves based on the north arrow and the scale. We also automate recording of geometric whole-outlines through contour detection, as an alternative to landmark-based geometric morphometrics. Detected objects, contours, and other automatically retrieved data can be manually validated and adjusted. We use third millennium BC Europe (encompassing cultures such as 'Corded Ware' and 'Bell Beaker', and their burial practices) as a 'testing ground' and for evaluation purposes; this includes a user study for the workflow and the AutArch software. △ Less

Submitted 15 February, 2024; v1 submitted 29 November, 2023; originally announced November 2023.

Simple Lattice Basis Computation -- The Generalization of the Euclidean Algorithm

Authors: Kim-Manuel Klein, Janina Reuter

Abstract: The Euclidean algorithm is one of the oldest algorithms known to mankind. Given two integral numbers $a_1$ and $a_2$, it computes the greatest common divisor (gcd) of $a_1$ and $a_2$ in a very elegant way. From a lattice perspective, it computes a basis of the sum of two one-dimensional lattices $a_1 \mathbb{Z}$ and $a_2 \mathbb{Z}$ as $\gcd(a_1,a_2) \mathbb{Z} = a_1 \mathbb{Z} + a_2 \mathbb{Z}$.… ▽ More The Euclidean algorithm is one of the oldest algorithms known to mankind. Given two integral numbers $a_1$ and $a_2$, it computes the greatest common divisor (gcd) of $a_1$ and $a_2$ in a very elegant way. From a lattice perspective, it computes a basis of the sum of two one-dimensional lattices $a_1 \mathbb{Z}$ and $a_2 \mathbb{Z}$ as $\gcd(a_1,a_2) \mathbb{Z} = a_1 \mathbb{Z} + a_2 \mathbb{Z}$. In this paper, we show that the classical Euclidean algorithm can be adapted in a very natural way to compute a basis of a general lattice $L(a_1, \ldots , a_m)$ given vectors $a_1, \ldots , a_m \in \mathbb{Z}^n$ with $m> \mathrm{rank}(a_1, \ldots ,a_m)$. Similar to the Euclidean algorithm, our algorithm is very easy to describe and implement and can be written within 12 lines of pseudocode. While the Euclidean algorithm halves the largest number in every iteration, our generalized algorithm halves the determinant of a full rank subsystem leading to at most $\log (\det B)$ many iterations, for some initial subsystem $B$. Therefore, we can compute a basis of the lattice using at most $\tilde{O}((m-n)n\log(\det B) + mn^{ω-1}\log(||A||_\infty))$ arithmetic operations, where $ω$ is the matrix multiplication exponent and $A = (a_1, \ldots, a_m)$. Even using the worst case Hadamard bound for the determinant, our algorithm improves upon existing algorithm. Another major advantage of our algorithm is that we can bound the entries of the resulting lattice basis by $\tilde{O}(n^2\cdot ||A||_{\infty})$ using a simple pivoting rule. This is in contrast to the typical approach for computing lattice basis, where the Hermite normal form (HNF) is used. In the HNF, entries can be as large as the determinant and hence can only be bounded by an exponential term. △ Less

Submitted 27 November, 2023; originally announced November 2023.

ACM Class: F.2.2; G.2.1

Deep Aramaic: Towards a Synthetic Data Paradigm Enabling Machine Learning in Epigraphy

Authors: Andrei C. Aioanei, Regine Hunziker-Rodewald, Konstantin Klein, Dominik L. Michels

Abstract: Epigraphy increasingly turns to modern artificial intelligence (AI) technologies such as machine learning (ML) for extracting insights from ancient inscriptions. However, scarce labeled data for training ML algorithms severely limits current techniques, especially for ancient scripts like Old Aramaic. Our research pioneers an innovative methodology for generating synthetic training data tailored t… ▽ More Epigraphy increasingly turns to modern artificial intelligence (AI) technologies such as machine learning (ML) for extracting insights from ancient inscriptions. However, scarce labeled data for training ML algorithms severely limits current techniques, especially for ancient scripts like Old Aramaic. Our research pioneers an innovative methodology for generating synthetic training data tailored to Old Aramaic letters. Our pipeline synthesizes photo-realistic Aramaic letter datasets, incorporating textural features, lighting, damage, and augmentations to mimic real-world inscription diversity. Despite minimal real examples, we engineer a dataset of 250,000 training and 25,000 validation images covering the 22 letter classes in the Aramaic alphabet. This comprehensive corpus provides a robust volume of data for training a residual neural network (ResNet) to classify highly degraded Aramaic letters. The ResNet model demonstrates high accuracy in classifying real images from the 8th century BCE Hadad statue inscription. Additional experiments validate performance on varying materials and styles, proving effective generalization. Our results validate the model's capabilities in handling diverse real-world scenarios, proving the viability of our synthetic data approach and avoiding the dependence on scarce training data that has constrained epigraphic analysis. Our innovative framework elevates interpretation accuracy on damaged inscriptions, thus enhancing knowledge extraction from these historical resources. △ Less

Submitted 11 October, 2023; originally announced October 2023.

Comments: 41 pages, 19 images

CelticGraph: Drawing Graphs as Celtic Knots and Links

Authors: Peter Eades, Niklas Gröne, Karsten Klein, Patrick Eades, Leo Schreiber, Ulf Hailer, Falk Schreiber

Abstract: Celtic knots are an ancient art form often attributed to Celtic cultures, used to decorate monuments and manuscripts, and to symbolise eternity and interconnectedness. This paper describes the framework CelticGraph to draw graphs as Celtic knots and links. The drawing process raises interesting combinatorial concepts in the theory of circuits in planar graphs. Further, CelticGraph uses a novel alg… ▽ More Celtic knots are an ancient art form often attributed to Celtic cultures, used to decorate monuments and manuscripts, and to symbolise eternity and interconnectedness. This paper describes the framework CelticGraph to draw graphs as Celtic knots and links. The drawing process raises interesting combinatorial concepts in the theory of circuits in planar graphs. Further, CelticGraph uses a novel algorithm to represent edges as Bézier curves, aiming to show each link as a smooth curve with limited curvature. △ Less

Submitted 14 September, 2023; v1 submitted 6 September, 2023; originally announced September 2023.

Comments: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

2D, 2.5D, or 3D? An Exploratory Study on Multilayer Network Visualisations in Virtual Reality

Authors: Stefan P. Feyer, Bruno Pinaud, Stephen G. Kobourov, Nicolas Brich, Michael Krone, Andreas Kerren, Michael Behrisch, Falk Schreiber, Karsten Klein

Abstract: Relational information between different types of entities is often modelled by a multilayer network (MLN) -- a network with subnetworks represented by layers. The layers of an MLN can be arranged in different ways in a visual representation, however, the impact of the arrangement on the readability of the network is an open question. Therefore, we studied this impact for several commonly occu… ▽ More Relational information between different types of entities is often modelled by a multilayer network (MLN) -- a network with subnetworks represented by layers. The layers of an MLN can be arranged in different ways in a visual representation, however, the impact of the arrangement on the readability of the network is an open question. Therefore, we studied this impact for several commonly occurring tasks related to MLN analysis. Additionally, layer arrangements with a dimensionality beyond 2D, which are common in this scenario, motivate the use of stereoscopic displays. We ran a human subject study utilising a Virtual Reality headset to evaluate 2D, 2.5D, and 3D layer arrangements. The study employs six analysis tasks that cover the spectrum of an MLN task taxonomy, from path finding and pattern identification to comparisons between and across layers. We found no clear overall winner. However, we explore the task-to-arrangement space and derive empirical-based recommendations on the effective use of 2D, 2.5D, and 3D layer arrangements for MLNs. △ Less

Submitted 13 September, 2023; v1 submitted 20 July, 2023; originally announced July 2023.

Journal ref: IEEE Transactions on Visualization and Computer Graphics, In press, To appear. Accepted to IEEE VIS 2023

Parametrised polyconvex hyperelasticity with physics-augmented neural networks

Authors: Dominik K. Klein, Fabian J. Roth, Iman Valizadeh, Oliver Weeger

Abstract: In the present work, neural networks are applied to formulate parametrised hyperelastic constitutive models. The models fulfill all common mechanical conditions of hyperelasticity by construction. In particular, partially input-convex neural network (pICNN) architectures are applied based on feed-forward neural networks. Receiving two different sets of input arguments, pICNNs are convex in one of… ▽ More In the present work, neural networks are applied to formulate parametrised hyperelastic constitutive models. The models fulfill all common mechanical conditions of hyperelasticity by construction. In particular, partially input-convex neural network (pICNN) architectures are applied based on feed-forward neural networks. Receiving two different sets of input arguments, pICNNs are convex in one of them, while for the other, they represent arbitrary relationships which are not necessarily convex. In this way, the model can fulfill convexity conditions stemming from mechanical considerations without being too restrictive on the functional relationship in additional parameters, which may not necessarily be convex. Two different models are introduced, where one can represent arbitrary functional relationships in the additional parameters, while the other is monotonic in the additional parameters. As a first proof of concept, the model is calibrated to data generated with two differently parametrised analytical potentials, whereby three different pICNN architectures are investigated. In all cases, the proposed model shows excellent performance. △ Less

Submitted 7 July, 2023; originally announced July 2023.

Advanced discretization techniques for hyperelastic physics-augmented neural networks

Authors: Marlon Franke, Dominik K. Klein, Oliver Weeger, Peter Betsch

Abstract: In the present work, advanced spatial and temporal discretization techniques are tailored to hyperelastic physics-augmented neural networks, i.e., neural network based constitutive models which fulfill all relevant mechanical conditions of hyperelasticity by construction. The framework takes into account the structure of neural network-based constitutive models, in particular, that their derivativ… ▽ More In the present work, advanced spatial and temporal discretization techniques are tailored to hyperelastic physics-augmented neural networks, i.e., neural network based constitutive models which fulfill all relevant mechanical conditions of hyperelasticity by construction. The framework takes into account the structure of neural network-based constitutive models, in particular, that their derivatives are more complex compared to analytical models. The proposed framework allows for convenient mixed Hu-Washizu like finite element formulations applicable to nearly incompressible material behavior. The key feature of this work is a tailored energy-momentum scheme for time discretization, which allows for energy and momentum preserving dynamical simulations. Both the mixed formulation and the energy-momentum discretization are applied in finite element analysis. For this, a hyperelastic physics-augmented neural network model is calibrated to data generated with an analytical potential. In all finite element simulations, the proposed discretization techniques show excellent performance. All of this demonstrates that, from a formal point of view, neural networks are essentially mathematical functions. As such, they can be applied in numerical methods as straightforwardly as analytical constitutive models. Nevertheless, their special structure suggests to tailor advanced discretization methods, to arrive at compact mathematical formulations and convenient implementations. △ Less

Submitted 16 June, 2023; originally announced June 2023.

Neural networks meet hyperelasticity: A guide to enforcing physics

Authors: Lennart Linden, Dominik K. Klein, Karl A. Kalina, Jörg Brummund, Oliver Weeger, Markus Kästner

Abstract: In the present work, a hyperelastic constitutive model based on neural networks is proposed which fulfills all common constitutive conditions by construction, and in particular, is applicable to compressible material behavior. Using different sets of invariants as inputs, a hyperelastic potential is formulated as a convex neural network, thus fulfilling symmetry of the stress tensor, objectivity,… ▽ More In the present work, a hyperelastic constitutive model based on neural networks is proposed which fulfills all common constitutive conditions by construction, and in particular, is applicable to compressible material behavior. Using different sets of invariants as inputs, a hyperelastic potential is formulated as a convex neural network, thus fulfilling symmetry of the stress tensor, objectivity, material symmetry, polyconvexity, and thermodynamic consistency. In addition, a physically sensible stress behavior of the model is ensured by using analytical growth terms, as well as normalization terms which ensure the undeformed state to be stress free and with zero energy. In particular, polyconvex, invariant-based stress normalization terms are formulated for both isotropic and transversely isotropic material behavior. By fulfilling all of these conditions in an exact way, the proposed physics-augmented model combines a sound mechanical basis with the extraordinary flexibility that neural networks offer. Thus, it harmonizes the theory of hyperelasticity developed in the last decades with the up-to-date techniques of machine learning. Furthermore, the non-negativity of the hyperelastic neural network-based potentials is numerically examined by sampling the space of admissible deformations states, which, to the best of the authors' knowledge, is the only possibility for the considered nonlinear compressible models. For the isotropic neural network model, the sampling space required for that is reduced by analytical considerations. In addition, a proof for the non-negativity of the compressible Neo-Hooke potential is presented. The applicability of the model is demonstrated by calibrating it on data generated with analytical potentials, which is followed by an application of the model to finite element simulations. In addition, an adaption of the model to noisy data is shown and its [...] △ Less

Submitted 6 July, 2023; v1 submitted 5 February, 2023; originally announced February 2023.

Journal ref: Journal of the Mechanics and Physics of Solids (2023)

Deep Learning-Based Assessment of Cerebral Microbleeds in COVID-19

Authors: Neus Rodeja Ferrer, Malini Vendela Sagar, Kiril Vadimovic Klein, Christina Kruuse, Mads Nielsen, Mostafa Mehdipour Ghazi

Abstract: Cerebral Microbleeds (CMBs), typically captured as hypointensities from susceptibility-weighted imaging (SWI), are particularly important for the study of dementia, cerebrovascular disease, and normal aging. Recent studies on COVID-19 have shown an increase in CMBs of coronavirus cases. Automatic detection of CMBs is challenging due to the small size and amount of CMBs making the classes highly im… ▽ More Cerebral Microbleeds (CMBs), typically captured as hypointensities from susceptibility-weighted imaging (SWI), are particularly important for the study of dementia, cerebrovascular disease, and normal aging. Recent studies on COVID-19 have shown an increase in CMBs of coronavirus cases. Automatic detection of CMBs is challenging due to the small size and amount of CMBs making the classes highly imbalanced, lack of publicly available annotated data, and similarity with CMB mimics such as calcifications, irons, and veins. Hence, the existing deep learning methods are mostly trained on very limited research data and fail to generalize to unseen data with high variability and cannot be used in clinical setups. To this end, we propose an efficient 3D deep learning framework that is actively trained on multi-domain data. Two public datasets assigned for normal aging, stroke, and Alzheimer's disease analysis as well as an in-house dataset for COVID-19 assessment are used to train and evaluate the models. The obtained results show that the proposed method is robust to low-resolution images and achieves 78% recall and 80% precision on the entire test set with an average false positive of 1.6 per scan. △ Less

Submitted 23 January, 2023; originally announced January 2023.

Comments: International Symposium on Biomedical Imaging (ISBI) 2023

On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs

Authors: Kim-Manuel Klein, Adam Polak, Lars Rohwedder

Abstract: The starting point of this paper is the problem of scheduling $n$ jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy jobs, i.e., $1||\sum p_j U_j$. This problem was identified by Bringmann et al. (Algorithmica 2022) as a natural subquadratic-time special case of the classic $1||\sum w_j U_j$ problem, which likely requires time quadrati… ▽ More The starting point of this paper is the problem of scheduling $n$ jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy jobs, i.e., $1||\sum p_j U_j$. This problem was identified by Bringmann et al. (Algorithmica 2022) as a natural subquadratic-time special case of the classic $1||\sum w_j U_j$ problem, which likely requires time quadratic in the total processing time $P$, because of a fine-grained lower bound. Bringmann et al.~obtain their $\tilde{O}(P^{7/4})$ time scheduling algorithm through a new variant of convolution, dubbed Max-Min Skewed Convolution, which they solve in $\tilde{O}(n^{7/4})$ time. Our main technical contribution is a faster and simpler convolution algorithm running in $\tilde{O}(n^{5/3})$ time. It implies an $\tilde{O}(P^{5/3})$ time algorithm for $1||\sum p_j U_j$, but may also be of independent interest. Inspired by recent developments for the Subset Sum and Knapsack problems, we study $1||\sum p_j U_j$ parameterized by the maximum job processing time $p_{\max}$. With proximity techniques borrowed from integer linear programming (ILP), we show structural properties of the problem that, coupled with a new dynamic programming formulation, lead to an $\tilde{O}(n+p_{\max}^3)$ time algorithm. Moreover, in the setting with multiple machines, we use similar techniques to get an $n \cdot p_{\max}^{O(m)}$ time algorithm for $Pm||\sum p_j U_j$. Finally, we point out that the considered problems exhibit a particular triangular block structure in the constraint matrices of their ILP formulations. In light of recent ILP research, a question that arises is whether one can devise a generic algorithm for such a class of ILPs. We give a negative answer to this question: we show that already a slight generalization of the structure of the scheduling ILP leads to a strongly NP-hard problem. △ Less

Submitted 10 November, 2022; v1 submitted 9 November, 2022; originally announced November 2022.

Comments: SODA 2023

Finite electro-elasticity with physics-augmented neural networks

Authors: Dominik K. Klein, Rogelio Ortigosa, Jesús Martínez-Frutos, Oliver Weeger

Abstract: In the present work, a machine learning based constitutive model for electro-mechanically coupled material behavior at finite deformations is proposed. Using different sets of invariants as inputs, an internal energy density is formulated as a convex neural network. In this way, the model fulfills the polyconvexity condition which ensures material stability, as well as thermodynamic consistency, o… ▽ More In the present work, a machine learning based constitutive model for electro-mechanically coupled material behavior at finite deformations is proposed. Using different sets of invariants as inputs, an internal energy density is formulated as a convex neural network. In this way, the model fulfills the polyconvexity condition which ensures material stability, as well as thermodynamic consistency, objectivity, material symmetry, and growth conditions. Depending on the considered invariants, this physics-augmented machine learning model can either be applied for compressible or nearly incompressible material behavior, as well as for arbitrary material symmetry classes. The applicability and versatility of the approach is demonstrated by calibrating it on transversely isotropic data generated with an analytical potential, as well as for the effective constitutive modeling of an analytically homogenized, transversely isotropic rank-one laminate composite and a numerically homogenized cubic metamaterial. These examinations show the excellent generalization properties that physics-augmented neural networks offer also for multi-physical material modeling such as nonlinear electro-elasticity. △ Less

Submitted 27 August, 2022; v1 submitted 10 June, 2022; originally announced June 2022.

Collapsing the Tower -- On the Complexity of Multistage Stochastic IPs

Authors: Kim-Manuel Klein, Janina Reuter

Abstract: In this paper we study the computational complexity of solving a class of block structured integer programs (IPs) - so called multistage stochastic IPs. A multistage stochastic IP is an IP of the form $\max \{ c^T x \mid \mathcal{A} x = b, \,l \leq x \leq u,\, x\text{ integral} \}$ where the constraint matrix $\mathcal{A}$ consists of small block matrices ordered on the diagonal line and for each… ▽ More In this paper we study the computational complexity of solving a class of block structured integer programs (IPs) - so called multistage stochastic IPs. A multistage stochastic IP is an IP of the form $\max \{ c^T x \mid \mathcal{A} x = b, \,l \leq x \leq u,\, x\text{ integral} \}$ where the constraint matrix $\mathcal{A}$ consists of small block matrices ordered on the diagonal line and for each stage there are larger blocks with few columns connecting the blocks in a tree like fashion. Over the last years there was enormous progress in the area of block structured IPs. For many of the known block IP classes - such as $n$-fold, tree-fold, and two-stage stochastic IPs, nearly matching upper and lower bounds are known concerning their computational complexity. One of the major gaps that remained however was the parameter dependency in the running time for an algorithm solving multistage stochastic IPs. Previous algorithms require a tower of $t$ exponentials, where $t$ is the number of stages, while only a double exponential lower bound was known. In this paper we show that the tower of $t$ exponentials is actually not necessary. We can show an improved running time for the algorithm solving multistage stochastic IPs with a running time of $2^{(d\||A||_\infty)^{\mathcal{O}(d^{3t+1})}} \cdot poly(d,n)$, where $d$ is the sum of columns in the connecting blocks and $n$ is the number of blocks on the lowest stage. In contrast to previous works, our algorithm has only a triple exponential dependency on the parameters and only doubly exponential for every constant $t$. By this we come very close the known double exponential bound (based on the exponential time hypothesis) that holds already for two-stage stochastic IPs, i.e. multistage stochastic IPs with only two stages. △ Less

Submitted 26 October, 2021; v1 submitted 25 October, 2021; originally announced October 2021.

Comments: 17 pages, 3 figures

On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem

Authors: Kim-Manuel Klein

Abstract: Consider positive integral solutions $x \in \mathbb{Z}^{n+1}$ to the equation $a_0 x_0 + \ldots + a_n x_n = t$. In the so called unbounded subset sum problem, the objective is to decide whether such a solution exists, whereas in the Frobenius problem, the objective is to compute the largest $t$ such that there is no such solution. In this paper we study the algorithmic complexity of the unbounde… ▽ More Consider positive integral solutions $x \in \mathbb{Z}^{n+1}$ to the equation $a_0 x_0 + \ldots + a_n x_n = t$. In the so called unbounded subset sum problem, the objective is to decide whether such a solution exists, whereas in the Frobenius problem, the objective is to compute the largest $t$ such that there is no such solution. In this paper we study the algorithmic complexity of the unbounded subset sum, the Frobenius problem and a generalization of the problems. More precisely, we study pseudo-polynomial time algorithms with a running time that depends on the smallest number $a_0$ or respectively the largest number $a_n$. For the parameter $a_0$, we show that all considered problems are subquadratically equivalent to $(min,+)$-convolution, a fundamental algorithmic problem from the area of fine-grained complexity. By this equivalence, we obtain hardness results for the considered problems (based on the assumption that an algorithm with a subquadratic running time for $(min,+)$-convolution does not exist) as well as algorithms with improved running time. The proof for the equivalence makes use of structural properties of solutions, a technique that was developed in the area of integer programming. In case of the complexity of the problems parameterized by $a_n$, we present improved algorithms. For example we give a quasi linear time algorithm for the Frobenius problem as well as a hardness result based on the strong exponential time hypothesis. △ Less

Submitted 12 August, 2021; originally announced August 2021.

Comments: 19 pages, 2 figures

ACM Class: F.2.2; F.2.3

Polyconvex anisotropic hyperelasticity with neural networks

Authors: Dominik K. Klein, Mauricio Fernández, Robert J. Martin, Patrizio Neff, Oliver Weeger

Abstract: In the present work, two machine learning based constitutive models for finite deformations are proposed. Using input convex neural networks, the models are hyperelastic, anisotropic and fulfill the polyconvexity condition, which implies ellipticity and thus ensures material stability. The first constitutive model is based on a set of polyconvex, anisotropic and objective invariants. The second ap… ▽ More In the present work, two machine learning based constitutive models for finite deformations are proposed. Using input convex neural networks, the models are hyperelastic, anisotropic and fulfill the polyconvexity condition, which implies ellipticity and thus ensures material stability. The first constitutive model is based on a set of polyconvex, anisotropic and objective invariants. The second approach is formulated in terms of the deformation gradient, its cofactor and determinant, uses group symmetrization to fulfill the material symmetry condition, and data augmentation to fulfill objectivity approximately. The extension of the dataset for the data augmentation approach is based on mechanical considerations and does not require additional experimental or simulation data. The models are calibrated with highly challenging simulation data of cubic lattice metamaterials, including finite deformations and lattice instabilities. A moderate amount of calibration data is used, based on deformations which are commonly applied in experimental investigations. While the invariant-based model shows drawbacks for several deformation modes, the model based on the deformation gradient alone is able to reproduce and predict the effective material behavior very well and exhibits excellent generalization capabilities. In addition, the models are calibrated with transversely isotropic data, generated with an analytical polyconvex potential. For this case, both models show excellent results, demonstrating the straightforward applicability of the polyconvex neural network constitutive models to other symmetry groups. △ Less

Submitted 25 November, 2021; v1 submitted 20 June, 2021; originally announced June 2021.

The Double Exponential Runtime is Tight for 2-Stage Stochastic ILPs

Authors: Klaus Jansen, Kim-Manuel Klein, Alexandra Lassota

Abstract: We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called $2$-stage stochastic. A $2$-stage stochastic ILP is an integer program of the form $\min \{c^T x \mid \mathcal{A} x = b, \ell \leq x \leq u, x \in \mathbb{Z}^{r + ns} \}$ where the constraint matrix $\mathcal{A} \in \mathbb{Z}^{nt \times r +ns}$ cons… ▽ More We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called $2$-stage stochastic. A $2$-stage stochastic ILP is an integer program of the form $\min \{c^T x \mid \mathcal{A} x = b, \ell \leq x \leq u, x \in \mathbb{Z}^{r + ns} \}$ where the constraint matrix $\mathcal{A} \in \mathbb{Z}^{nt \times r +ns}$ consists of $n$ matrices $A_i \in \mathbb{Z}^{t \times r}$ on the vertical line and $n$ matrices $B_i \in \mathbb{Z}^{t \times s}$ on the diagonal line aside. First, we show a stronger hardness result for a number theoretic problem called Quadratic Congruences where the objective is to compute a number $z \leq γ$ satisfying $z^2 \equiv α\bmod β$ for given $α, β, γ\in \mathbb{Z}$. This problem was proven to be NP-hard already in 1978 by Manders and Adleman. However, this hardness only applies for instances where the prime factorization of $β$ admits large multiplicities of each prime number. We circumvent this necessity proving that the problem remains NP-hard, even if each prime number only occurs constantly often. Then, using this new hardness result for the Quadratic Congruences problem, we prove a lower bound of $2^{2^{δ(s+t)}} |I|^{O(1)}$ for some $δ> 0$ for the running time of any algorithm solving $2$-stage stochastic ILPs assuming the Exponential Time Hypothesis (ETH). Here, $|I|$ is the encoding length of the instance. This result even holds if $r$, $||b||_{\infty}$, $||c||_{\infty}, ||\ell||_{\infty}$ and the largest absolute value $Δ$ in the constraint matrix $\mathcal{A}$ are constant. This shows that the state-of-the-art algorithms are nearly tight. Further, it proves the suspicion that these ILPs are indeed harder to solve than the closely related $n$-fold ILPs where the contraint matrix is the transpose of $\mathcal A$. △ Less

Submitted 5 February, 2021; v1 submitted 29 August, 2020; originally announced August 2020.

On Turn-Regular Orthogonal Representations

Authors: Michael A. Bekos, Carla Binucci, Giuseppe Di Battista, Walter Didimo, Martin Gronemann, Karsten Klein, Maurizio Patrignani, Ignaz Rutter

Abstract: An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other" inside a face. For such a representation H it is possible to compute in linear time a minimum-area drawing, i.e., a drawing of minimum area over all possible assignments of vertex and bend coordinates of H. In contrast… ▽ More An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other" inside a face. For such a representation H it is possible to compute in linear time a minimum-area drawing, i.e., a drawing of minimum area over all possible assignments of vertex and bend coordinates of H. In contrast, finding a minimum-area drawing of H is NP-hard if H is non-turn-regular. This scenario naturally motivates the study of which graphs admit turn-regular orthogonal representations. In this paper we identify notable classes of biconnected planar graphs that always admit such representations, which can be computed in linear time. We also describe a linear-time testing algorithm for trees and provide a polynomial-time algorithm that tests whether a biconnected plane graph with "small" faces has a turn-regular orthogonal representation without bends. △ Less

Submitted 20 August, 2020; originally announced August 2020.

Comments: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

New Bounds for the Vertices of the Integer Hull

Authors: Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein

Abstract: The vertices of the integer hull are the integral equivalent to the well-studied basic feasible solutions of linear programs. In this paper we give new bounds on the number of non-zero components -- their support -- of these vertices matching either the best known bounds or improving upon them. While the best known bounds make use of deep techniques, we only use basic results from probability theo… ▽ More The vertices of the integer hull are the integral equivalent to the well-studied basic feasible solutions of linear programs. In this paper we give new bounds on the number of non-zero components -- their support -- of these vertices matching either the best known bounds or improving upon them. While the best known bounds make use of deep techniques, we only use basic results from probability theory to make use of the concentration of measure effect. To show the versatility of our techniques, we use our results to give the best known bounds on the number of such vertices and an algorithm to enumerate them. We also improve upon the known lower bounds to show that our results are nearly optimal. One of the main ingredients of our work is a generalization of the famous Hoeffding bound to vector-valued random variables that might be of general interest. △ Less

Submitted 18 June, 2020; originally announced June 2020.

Fuzzy Simultaneous Congruences

Authors: Max A. Deppert, Klaus Jansen, Kim-Manuel Klein

Abstract: We introduce a very natural generalization of the well-known problem of simultaneous congruences. Instead of searching for a positive integer $s$ that is specified by $n$ fixed remainders modulo integer divisors $a_1,\dots,a_n$ we consider remainder intervals $R_1,\dots,R_n$ such that $s$ is feasible if and only if $s$ is congruent to $r_i$ modulo $a_i$ for some remainder $r_i$ in interval $R_i$ f… ▽ More We introduce a very natural generalization of the well-known problem of simultaneous congruences. Instead of searching for a positive integer $s$ that is specified by $n$ fixed remainders modulo integer divisors $a_1,\dots,a_n$ we consider remainder intervals $R_1,\dots,R_n$ such that $s$ is feasible if and only if $s$ is congruent to $r_i$ modulo $a_i$ for some remainder $r_i$ in interval $R_i$ for all $i$. This problem is a special case of a 2-stage integer program with only two variables per constraint which is is closely related to directed Diophantine approximation as well as the mixing set problem. We give a hardness result showing that the problem is NP-hard in general. By investigating the case of harmonic divisors, i.e. $a_{i+1}/a_i$ is an integer for all $i<n$, which was heavily studied for the mixing set problem as well, we also answer a recent algorithmic question from the field of real-time systems. We present an algorithm to decide the feasibility of an instance in time $\mathcal{O}(n^2)$ and we show that if it exists even the smallest feasible solution can be computed in strongly polynomial time $\mathcal{O}(n^3)$. △ Less

Submitted 18 November, 2020; v1 submitted 18 February, 2020; originally announced February 2020.

A Study of Mental Maps in Immersive Network Visualization

Authors: Joseph Kotlarek, Oh-Hyun Kwon, Kwan-Liu Ma, Peter Eades, Andreas Kerren, Karsten Klein, Falk Schreiber

Abstract: The visualization of a network influences the quality of the mental map that the viewer develops to understand the network. In this study, we investigate the effects of a 3D immersive visualization environment compared to a traditional 2D desktop environment on the comprehension of a network's structure. We compare the two visualization environments using three tasks--interpreting network structur… ▽ More The visualization of a network influences the quality of the mental map that the viewer develops to understand the network. In this study, we investigate the effects of a 3D immersive visualization environment compared to a traditional 2D desktop environment on the comprehension of a network's structure. We compare the two visualization environments using three tasks--interpreting network structure, memorizing a set of nodes, and identifying the structural changes--commonly used for evaluating the quality of a mental map in network visualization. The results show that participants were able to interpret network structure more accurately when viewing the network in an immersive environment, particularly for larger networks. However, we found that 2D visualizations performed better than immersive visualization for tasks that required spatial memory. △ Less

Submitted 17 January, 2020; originally announced January 2020.

Comments: IEEE Pacific Visualization Symposium 2020

An Algorithmic Theory of Integer Programming

Authors: Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Asaf Levin, Shmuel Onn

Abstract: We study the general integer programming problem where the number of variables $n$ is a variable part of the input. We consider two natural parameters of the constraint matrix $A$: its numeric measure $a$ and its sparsity measure $d$. We show that integer programming can be solved in time $g(a,d)\textrm{poly}(n,L)$, where $g$ is some computable function of the parameters $a$ and $d$, and $L$ is th… ▽ More We study the general integer programming problem where the number of variables $n$ is a variable part of the input. We consider two natural parameters of the constraint matrix $A$: its numeric measure $a$ and its sparsity measure $d$. We show that integer programming can be solved in time $g(a,d)\textrm{poly}(n,L)$, where $g$ is some computable function of the parameters $a$ and $d$, and $L$ is the binary encoding length of the input. In particular, integer programming is fixed-parameter tractable parameterized by $a$ and $d$, and is solvable in polynomial time for every fixed $a$ and $d$. Our results also extend to nonlinear separable convex objective functions. Moreover, for linear objectives, we derive a strongly-polynomial algorithm, that is, with running time $g(a,d)\textrm{poly}(n)$, independent of the rest of the input data. We obtain these results by developing an algorithmic framework based on the idea of iterative augmentation: starting from an initial feasible solution, we show how to quickly find augmenting steps which rapidly converge to an optimum. A central notion in this framework is the Graver basis of the matrix $A$, which constitutes a set of fundamental augmenting steps. The iterative augmentation idea is then enhanced via the use of other techniques such as new and improved bounds on the Graver basis, rapid solution of integer programs with bounded variables, proximity theorems and a new proximity-scaling algorithm, the notion of a reduced objective function, and others. As a consequence of our work, we advance the state of the art of solving block-structured integer programs. In particular, we develop near-linear time algorithms for $n$-fold, tree-fold, and $2$-stage stochastic integer programs. We also discuss some of the many applications of these classes. △ Less

Submitted 29 July, 2022; v1 submitted 2 April, 2019; originally announced April 2019.

Comments: Revision 3: - corrections to specified complexities (infinite bounds, feasibility, etc.)

MSC Class: 15A; 52B; 52C; 68Q; 68R; 68W; 90B; 90C ACM Class: F.2.2; G.1.6

About the Complexity of Two-Stage Stochastic IPs

Authors: Kim-Manuel Klein

Abstract: We consider so called $2$-stage stochastic integer programs (IPs) and their generalized form of multi-stage stochastic IPs. A $2$-stage stochastic IP is an integer program of the form $\max \{ c^T x \mid Ax = b, l \leq x \leq u, x \in \mathbb{Z}^{nt + s} \}$ where the constraint matrix $A \in \mathbb{Z}^{r \times s}$ consists roughly of $n$ repetition of a block matrix $A$ on the vertical line and… ▽ More We consider so called $2$-stage stochastic integer programs (IPs) and their generalized form of multi-stage stochastic IPs. A $2$-stage stochastic IP is an integer program of the form $\max \{ c^T x \mid Ax = b, l \leq x \leq u, x \in \mathbb{Z}^{nt + s} \}$ where the constraint matrix $A \in \mathbb{Z}^{r \times s}$ consists roughly of $n$ repetition of a block matrix $A$ on the vertical line and $n$ repetitions of a matrix $B \in \mathbb{Z}^{r \times t}$ on the diagonal. In this paper we improve upon an algorithmic result by Hemmecke and Schultz form 2003 to solve $2$-stage stochastic IPs. The algorithm is based on the Graver augmentation framework where our main contribution is to give an explicit doubly exponential bound on the size of the augmenting steps. The previous bound for the size of the augmenting steps relied on non-constructive finiteness arguments from commutative algebra and therefore only an implicit bound was known that depends on parameters $r,s,t$ and $Δ$, where $Δ$ is the largest entry of the constraint matrix. Our new improved bound however is obtained by a novel theorem which argues about the intersection of paths in a vector space. As a result of our new bound we obtain an algorithm to solve $2$-stage stochastic IPs in time $poly(n,t) \cdot f(r,s,Δ)$, where $f$ is a doubly exponential function. To complement our result, we also prove a doubly exponential lower bound for the size of the augmenting steps. △ Less

Submitted 21 February, 2019; v1 submitted 4 January, 2019; originally announced January 2019.

An EPTAS for machine scheduling with bag-constraints

Authors: Kilian Grage, Klaus Jansen, Kim Manuel Klein

Abstract: Machine scheduling is a fundamental optimization problem in computer science. The task of scheduling a set of jobs on a given number of machines and minimizing the makespan is well studied and among other results, we know that EPTAS's for machine scheduling on identical machines exist. Das and Wiese initiated the research on a generalization of makespan minimization, that includes so called bag-co… ▽ More Machine scheduling is a fundamental optimization problem in computer science. The task of scheduling a set of jobs on a given number of machines and minimizing the makespan is well studied and among other results, we know that EPTAS's for machine scheduling on identical machines exist. Das and Wiese initiated the research on a generalization of makespan minimization, that includes so called bag-constraints. In this variation of machine scheduling the given set of jobs is partitioned into subsets, so called bags. Given this partition a schedule is only considered feasible when on any machine there is at most one job from each bag. Das and Wiese showed that this variant of machine scheduling admits a PTAS. We will improve on this result by giving the first EPTAS for the machine scheduling problem with bag-constraints. We achieve this result by using new insights on this problem and restrictions given by the bag-constraints. We show that, to gain an approximate solution, we can relax the bag-constraints and ignore some of the restrictions. Our EPTAS uses a new instance transformation that will allow us to schedule large and small jobs independently of each other for a majority of bags. We also show that it is sufficient to respect the bag-constraint only among a constant number of bags, when scheduling large jobs. With these observations our algorithm will allow for some conflicts when computing a schedule and we show how to repair the schedule in polynomial-time by swapping certain jobs around. △ Less

Submitted 17 October, 2018; originally announced October 2018.

Exploring the Limits of Complexity: A Survey of Empirical Studies on Graph Visualisation

Authors: Vahan Yoghourdjian, Daniel Archambault, Stephan Diehl, Tim Dwyer, Karsten Klein, Helen C. Purchase, Hsiang-Yun Wu

Abstract: For decades, researchers in information visualisation and graph drawing have focused on developing techniques for the layout and display of very large and complex networks. Experiments involving human participants have also explored the readability of different styles of layout and representations for such networks. In both bodies of literature, networks are frequently referred to as being 'large'… ▽ More For decades, researchers in information visualisation and graph drawing have focused on developing techniques for the layout and display of very large and complex networks. Experiments involving human participants have also explored the readability of different styles of layout and representations for such networks. In both bodies of literature, networks are frequently referred to as being 'large' or 'complex', yet these terms are relative. From a human-centred, experiment point-of-view, what constitutes 'large' (for example) depends on several factors, such as data complexity, visual complexity, and the technology used. In this paper, we survey the literature on human-centred experiments to understand how, in practice, different features and characteristics of node-link diagrams affect visual complexity. △ Less

Submitted 1 September, 2018; originally announced September 2018.

Turning Cliques into Paths to Achieve Planarity

Authors: Patrizio Angelini, Peter Eades, Seok-Hee Hong, Karsten Klein, Stephen Kobourov, Giuseppe Liotta, Alfredo Navarra, Alessandra Tappini

Abstract: Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call $h$-Clique2Path Planarity: Given a graph $G$, whose vertices are partitioned into subsets of size at most $h$, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of $G$ is planar.… ▽ More Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call $h$-Clique2Path Planarity: Given a graph $G$, whose vertices are partitioned into subsets of size at most $h$, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of $G$ is planar. We study this problem when $G$ is a simple topological graph, and establish its complexity in relation to $k$-planarity. We prove that $h$-Clique2Path Planarity is NP-complete even when $h=4$ and $G$ is a simple $3$-plane graph, while it can be solved in linear time, for any $h$, when $G$ is $1$-plane. △ Less

Submitted 28 August, 2018; v1 submitted 27 August, 2018; originally announced August 2018.

Comments: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

Faster Algorithms for Integer Programs with Block Structure

Authors: Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein

Abstract: We consider integer programming problems $\max \{ c^T x : \mathcal{A} x = b, l \leq x \leq u, x \in \mathbb{Z}^{nt}\}$ where $\mathcal{A}$ has a (recursive) block-structure generalizing "$n$-fold integer programs" which recently received considerable attention in the literature. An $n$-fold IP is an integer program where $\mathcal{A}$ consists of $n$ repetitions of submatrices… ▽ More We consider integer programming problems $\max \{ c^T x : \mathcal{A} x = b, l \leq x \leq u, x \in \mathbb{Z}^{nt}\}$ where $\mathcal{A}$ has a (recursive) block-structure generalizing "$n$-fold integer programs" which recently received considerable attention in the literature. An $n$-fold IP is an integer program where $\mathcal{A}$ consists of $n$ repetitions of submatrices $A \in \mathbb{Z}^{r \times t}$ on the top horizontal part and $n$ repetitions of a matrix $B \in \mathbb{Z}^{s \times t}$ on the diagonal below the top part. Instead of allowing only two types of block matrices, one for the horizontal line and one for the diagonal, we generalize the $n$-fold setting to allow for arbitrary matrices in every block. We show that such an integer program can be solved in time $n^2 t^2 φ \cdot (rsΔ)^{\mathcal{O}(rs^2+ sr^2)}$ (ignoring logarithmic factors). Here $Δ$ is an upper bound on the largest absolute value of an entry of $\mathcal{A}$ and $φ$ is the largest binary encoding length of a coefficient of $c$. This improves upon the previously best algorithm of Hemmecke, Onn and Romanchuk that runs in time $n^3t^3 φ \cdot Δ^{\mathcal{O}(t^2s)}$. In particular, our algorithm is not exponential in the number $t$ of columns of $A$ and $B$. Our algorithm is based on a new upper bound on the $l_1$-norm of an element of the "Graver basis" of an integer matrix and on a proximity bound between the LP and IP optimal solutions tailored for IPs with block structure. These new bounds rely on the "Steinitz Lemma". Furthermore, we extend our techniques to the recently introduced "tree-fold IPs", where we again present a more efficient algorithm in a generalized setting. △ Less

Submitted 17 February, 2018; originally announced February 2018.

Empowering the Configuration-IP $-$ New PTAS Results for Scheduling with Setups Times

Authors: Klaus Jansen, Kim-Manuel Klein, Marten Maack, Malin Rau

Abstract: Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems, where a set of items has to be placed in multiple target locations. Herein a configuration describes a possible placement on one of the target locations, and the IP is used to chose suitable configurations covering the items. We give an augmented IP… ▽ More Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems, where a set of items has to be placed in multiple target locations. Herein a configuration describes a possible placement on one of the target locations, and the IP is used to chose suitable configurations covering the items. We give an augmented IP formulation, which we call the module configuration IP. It can be described within the framework of n-fold integer programming and therefore be solved efficiently. As an application, we consider scheduling problems with setup times, in which a set of jobs has to be scheduled on a set of identical machines, with the objective of minimizing the makespan. For instance, we investigate the case that jobs can be split and scheduled on multiple machines. However, before a part of a job can be processed an uninterrupted setup depending on the job has to be paid. For both of the variants that jobs can be executed in parallel or not, we obtain an efficient polynomial time approximation scheme (EPTAS) of running time $f(1/\varepsilon)\times \mathrm{poly}(|I|)$ with a single exponential term in $f$ for the first and a double exponential one for the second case. Previously, only constant factor approximations of $5/3$ and $4/3 + \varepsilon$ respectively were known. Furthermore, we present an EPTAS for a problem where classes of (non-splittable) jobs are given, and a setup has to be paid for each class of jobs being executed on one machine. △ Less

Submitted 16 November, 2018; v1 submitted 19 January, 2018; originally announced January 2018.

Online Strip Packing with Polynomial Migration

Authors: Klaus Jansen, Kim-Manuel Klein, Maria Kosche, Leon Ladewig

Abstract: We consider the relaxed online strip packing problem: Rectangular items arrive online and have to be packed without rotations into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item… ▽ More We consider the relaxed online strip packing problem: Rectangular items arrive online and have to be packed without rotations into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio $1 + \mathcal{O}(ε)$ for any $ε> 0$ and amortized migration factor polynomial in $1 / ε$. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model. △ Less

Submitted 20 February, 2018; v1 submitted 15 June, 2017; originally announced June 2017.

Comments: An extended abstract of the paper has been published in APPROX 2017

High-Dimensional Data Visualization by Interactive Construction of Low-Dimensional Parallel Coordinate Plots

Authors: Takayuki Itoh, Ashnil Kumar, Karsten Klein, Jinman Kim

Abstract: Parallel coordinate plots (PCPs) are among the most useful techniques for the visualization and exploration of high-dimensional data spaces. They are especially useful for the representation of correlations among the dimensions, which identify relationships and interdependencies between variables. However, within these high-dimensional spaces, PCPs face difficulties in displaying the correlation b… ▽ More Parallel coordinate plots (PCPs) are among the most useful techniques for the visualization and exploration of high-dimensional data spaces. They are especially useful for the representation of correlations among the dimensions, which identify relationships and interdependencies between variables. However, within these high-dimensional spaces, PCPs face difficulties in displaying the correlation between combinations of dimensions and generally require additional display space as the number of dimensions increases. In this paper, we present a new technique for high-dimensional data visualization in which a set of low-dimensional PCPs are interactively constructed by sampling user-selected subsets of the high-dimensional data space. In our technique, we first construct a graph visualization of sets of well-correlated dimensions. Users observe this graph and are able to interactively select the dimensions by sampling from its cliques, thereby dynamically specifying the most relevant lower dimensional data to be used for the construction of focused PCPs. Our interactive sampling overcomes the shortcomings of the PCPs by enabling the visualization of the most meaningful dimensions (i.e., the most relevant information) from high-dimensional spaces. We demonstrate the effectiveness of our technique through two case studies, where we show that the proposed interactive low-dimensional space constructions were pivotal for visualizing the high-dimensional data and discovering new patterns. △ Less

Submitted 16 September, 2016; originally announced September 2016.

A Note on the Practicality of Maximal Planar Subgraph Algorithms

Authors: Markus Chimani, Karsten Klein, Tilo Wiedera

Abstract: Given a graph $G$, the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of $G$ with the maximum number of edges. There are several heuristic, approximative, and exact algorithms to tackle the problem, but---to the best of our knowledge---they have never been compared competitively in practice. We report on an exploratory study on the relative merits of the diverse approache… ▽ More Given a graph $G$, the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of $G$ with the maximum number of edges. There are several heuristic, approximative, and exact algorithms to tackle the problem, but---to the best of our knowledge---they have never been compared competitively in practice. We report on an exploratory study on the relative merits of the diverse approaches, focusing on practical runtime, solution quality, and implementation complexity. Surprisingly, a seemingly only theoretically strong approximation forms the building block of the strongest choice. △ Less

Submitted 26 August, 2016; originally announced August 2016.

Comments: Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

About the Structure of the Integer Cone and its Application to Bin Packing

Authors: Klaus Jansen, Kim-Manuel Klein

Abstract: We consider the bin packing problem with $d$ different item sizes and revisit the structure theorem given by Goemans and Rothvoß[6] about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for… ▽ More We consider the bin packing problem with $d$ different item sizes and revisit the structure theorem given by Goemans and Rothvoß[6] about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for the bin packing problem with running time $|V|^{2^{O(d)}} \cdot enc(I)^{O(1)}$, where $V$ is the set of vertices of the integer knapsack polytope and $enc(I)$ is the encoding length of the bin packing instance. The algorithm is fixed parameter tractable, parameterized by the number of vertices of the integer knapsack polytope $|V|$. This shows that the bin packing problem can be solved efficiently when the underlying integer knapsack polytope has an easy structure, i.e. has a small number of vertices. Furthermore, we show that the presented bounds of the structure theorem are asymptotically tight. We give a construction of bin packing instances using new structural insights and classical number theoretical theorems which yield the desired lower bound. △ Less

Submitted 8 December, 2016; v1 submitted 25 April, 2016; originally announced April 2016.

Comments: 18 pages, 1 figure

ACM Class: F.2.2

Closing the Gap for Makespan Scheduling via Sparsification Techniques

Authors: Klaus Jansen, Kim-Manuel Klein, José Verschae

Abstract: Makespan scheduling on identical machines is one of the most basic and fundamental packing problems studied in the discrete optimization literature. It asks for an assignment of $n$ jobs to a set of $m$ identical machines that minimizes the makespan. The problem is strongly NP-hard, and thus we do not expect a $(1+ε)$-approximation algorithm with a running time that depends polynomially on $1/ε$.… ▽ More Makespan scheduling on identical machines is one of the most basic and fundamental packing problems studied in the discrete optimization literature. It asks for an assignment of $n$ jobs to a set of $m$ identical machines that minimizes the makespan. The problem is strongly NP-hard, and thus we do not expect a $(1+ε)$-approximation algorithm with a running time that depends polynomially on $1/ε$. Furthermore, Chen et al. [3] recently showed that a running time of $2^{(1/ε)^{1-δ}}+\text{poly}(n)$ for any $δ>0$ would imply that the Exponential Time Hypothesis (ETH) fails. A long sequence of algorithms have been developed that try to obtain low dependencies on $1/ε$, the better of which achieves a running time of $2^{\tilde{O}(1/ε^2)}+O(n\log n)$ [11]. In this paper we obtain an algorithm with a running time of $2^{\tilde{O}(1/ε)}+O(n\log n)$, which is tight under ETH up to logarithmic factors on the exponent. Our main technical contribution is a new structural result on the configuration-IP. More precisely, we show the existence of a highly symmetric and sparse optimal solution, in which all but a constant number of machines are assigned a configuration with small support. This structure can then be exploited by integer programming techniques and enumeration. We believe that our structural result is of independent interest and should find applications to other settings. In particular, we show how the structure can be applied to the minimum makespan problem on related machines and to a larger class of objective functions on parallel machines. For all these cases we obtain an efficient PTAS with running time $2^{\tilde{O}(1/ε)} + \text{poly}(n)$. △ Less

Submitted 25 April, 2016; originally announced April 2016.

Comments: 20 pages, ICALP 2016

ACM Class: F.2.2

Fully Dynamic Bin Packing Revisited

Authors: Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein

Abstract: We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items… ▽ More We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ration of $1 + ε$ for the number of bins, a relatively simple argument proves a lower bound of $Ω(\frac{1}ε)$ for the migration factor. We establish a nearly matching upper bound of $O(\frac{1}ε^4 \log \frac{1}ε)$ using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items $n$ and in $\frac{1}ε$. The previous best trade-off was for an asymptotic competitive ratio of $\frac{5}{4}$ for the bins (rather than $1+ε$) and needed an amortized number of $O(\log n)$ repackings (while in our scheme the number of repackings is independent of $n$ and non-amortized). △ Less

Submitted 14 January, 2015; v1 submitted 4 November, 2014; originally announced November 2014.

ACM Class: F.2.2

Advances on Testing C-Planarity of Embedded Flat Clustered Graphs

Authors: Markus Chimani, Giuseppe Di Battista, Fabrizio Frati, Karsten Klein

Abstract: We show a polynomial-time algorithm for testing c-planarity of embedded flat clustered graphs with at most two vertices per cluster on each face. We show a polynomial-time algorithm for testing c-planarity of embedded flat clustered graphs with at most two vertices per cluster on each face. △ Less

Submitted 11 August, 2014; originally announced August 2014.

Comments: Accepted at GD '14

Trackability with Imprecise Localization

Authors: Kyle Klein, Subhash Suri

Abstract: Imagine a tracking agent $P$ who wants to follow a moving target $Q$ in $d$-dimensional Euclidean space. The tracker has access to a noisy location sensor that reports an estimate $\tilde{Q}(t)$ of the target's true location $Q(t)$ at time $t$, where $||Q(T) - \tilde{Q}(T)||$ represents the sensor's localization error. We study the limits of tracking performance under this kind of sensing imprecis… ▽ More Imagine a tracking agent $P$ who wants to follow a moving target $Q$ in $d$-dimensional Euclidean space. The tracker has access to a noisy location sensor that reports an estimate $\tilde{Q}(t)$ of the target's true location $Q(t)$ at time $t$, where $||Q(T) - \tilde{Q}(T)||$ represents the sensor's localization error. We study the limits of tracking performance under this kind of sensing imprecision. In particular, we investigate (1) what is $P$'s best strategy to follow $Q$ if both $P$ and $Q$ can move with equal speed, (2) at what rate does the distance $||Q(t) - P(t)||$ grow under worst-case localization noise, (3) if $P$ wants to keep $Q$ within a prescribed distance $L$, how much faster does it need to move, and (4) what is the effect of obstacles on the tracking performance, etc. Under a relative error model of noise, we are able to give upper and lower bounds for the worst-case tracking performance, both with or without obstacles. △ Less

Submitted 19 December, 2013; originally announced December 2013.

Comments: 17 pages, 9 figures

ACM Class: I.2.9

A Robust AFPTAS for Online Bin Packing with Polynomial Migration

Authors: Klaus Jansen, Kim-Manuel Klein

Abstract: In this paper we develop general LP and ILP techniques to find an approximate solution with improved objective value close to an existing solution. The task of improving an approximate solution is closely related to a classical theorem of Cook et al. in the sensitivity analysis for LPs and ILPs. This result is often applied in designing robust algorithms for online problems. We apply our new techn… ▽ More In this paper we develop general LP and ILP techniques to find an approximate solution with improved objective value close to an existing solution. The task of improving an approximate solution is closely related to a classical theorem of Cook et al. in the sensitivity analysis for LPs and ILPs. This result is often applied in designing robust algorithms for online problems. We apply our new techniques to the online bin packing problem, where it is allowed to reassign a certain number of items, measured by the migration factor. The migration factor is defined by the total size of reassigned items divided by the size of the arriving item. We obtain a robust asymptotic fully polynomial time approximation scheme (AFPTAS) for the online bin packing problem with migration factor bounded by a polynomial in $\frac{1}ε$. This answers an open question stated by Epstein and Levin in the affirmative. As a byproduct we prove an approximate variant of the sensitivity theorem by Cook at el. for linear programs. △ Less

Submitted 18 February, 2013; originally announced February 2013.

ACM Class: F.2.2

Capturing an Evader in Polygonal Environments: A Complete Information Game

Authors: Kyle Klein, Subhash Suri

Abstract: Suppose an unpredictable evader is free to move around in a polygonal environment of arbitrary complexity that is under full camera surveillance. How many pursuers, each with the same maximum speed as the evader, are necessary and sufficient to guarantee a successful capture of the evader? The pursuers always know the evader's current position through the camera network, but need to physically rea… ▽ More Suppose an unpredictable evader is free to move around in a polygonal environment of arbitrary complexity that is under full camera surveillance. How many pursuers, each with the same maximum speed as the evader, are necessary and sufficient to guarantee a successful capture of the evader? The pursuers always know the evader's current position through the camera network, but need to physically reach the evader to capture it. We allow the evader the knowledge of the current positions of all the pursuers as well---this accords with the standard worst-case analysis model, but also models a practical situation where the evader has "hacked" into the surveillance system. Our main result is to prove that three pursuers are always sufficient and sometimes necessary to capture the evader. The bound is independent of the number of vertices or holes in the polygonal environment. The result should be contrasted with the incomplete information pursuit-evasion where at least Ω(\surd h + log n) pursuers are required just for detecting the evader in an environment with n vertices and h holes. △ Less

Submitted 21 October, 2011; originally announced October 2011.

Comments: 17 pages, 12 figures

ACM Class: I.2.11; I.2.9

Journal ref: K. Klein and S. Suri. Complete information pursuit evasion in polygonal environments. In 25th Conference on Artificial Intelligence (AAAI), pages 1120--1125, 2011

The Open Graph Archive: A Community-Driven Effort

Authors: Christian Bachmaier, Franz J. Brandenburg, Philip Effinger, Carsten Gutwenger, Jyrki Katajainen, Karsten Klein, Miro Spönemann, Matthias Stegmaier, Michael Wybrow

Abstract: In order to evaluate, compare, and tune graph algorithms, experiments on well designed benchmark sets have to be performed. Together with the goal of reproducibility of experimental results, this creates a demand for a public archive to gather and store graph instances. Such an archive would ideally allow annotation of instances or sets of graphs with additional information like graph properties a… ▽ More In order to evaluate, compare, and tune graph algorithms, experiments on well designed benchmark sets have to be performed. Together with the goal of reproducibility of experimental results, this creates a demand for a public archive to gather and store graph instances. Such an archive would ideally allow annotation of instances or sets of graphs with additional information like graph properties and references to the respective experiments and results. Here we examine the requirements, and introduce a new community project with the aim of producing an easily accessible library of graphs. Through successful community involvement, it is expected that the archive will contain a representative selection of both real-world and generated graph instances, covering significant application areas as well as interesting classes of graphs. △ Less

Submitted 7 September, 2011; originally announced September 2011.

Comments: 10 pages