Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks
2016-10-31, Brandes, Ulrik, Holm, Eugenia, Karrenbauer, Andreas
The existence of a densely knit core surrounded by a loosely connected periphery is a common macro-structural feature of social networks. Formally, the CorePeriphery problem is to partition the nodes of an undirected graph G=(V,E) such that a subset X⊂V, the core, induces a dense subgraph, and its complement V∖X , the periphery, induces a sparse subgraph. Split graphs represent the ideal case in which the core induces a clique and the periphery forms an independent set. The number of missing and superfluous edges in the core and the periphery, respectively, can be minimized in linear time via edit distance to the closest split graph. We show that the CorePeriphery becomes intractable for standard notions of density other than the absolute number of misclassified pairs. Our main tool is a regularization procedure that transforms a given graph with maximum degree d into a d-regular graph with the same clique number by adding at most d⋅n new nodes. This is of independent interest because it implies that finding a maximum clique in a regular graph is NP-hard to approximate to within a factor of n1/2−ε for all ε>0 . We gratefully acknowledge financial support from Deutsche Forschungsgemeinschaft (DFG) under grants Br 2158/6-1 and Ka 3042/3-1. This work is partially supported by the Zukunftskolleg of the University of Konstanz, and the Max Planck Center for Visual Computing and Communication (www.mpc-vcc.org).
On Guillotine Cutting Sequences
2015, Abed, Fidaa, Chalermsook, Parinya, Correa, José, Karrenbauer, Andreas, Pérez-Lantero, Pablo, Soto, José A., Wiese, Andreas
Imagine a wooden plate with a set of non-overlapping geometric objects painted on it. How many of them can a carpenter cut out using a panel saw making guillotine cuts, i.e., only moving forward through the material along a straight line until it is split into two pieces? Already fifteen years ago, Pach and Tardos investigated whether one can always cut out a constant fraction if all objects are axis-parallel rectangles. However, even for the case of axis-parallel squares this question is still open. In this paper, we answer the latter affirmatively. Our result is constructive and holds even in a more general setting where the squares have weights and the goal is to save as much weight as possible. We further show that when solving the more general question for rectangles affirmatively with only axis-parallel cuts, this would yield a combinatorial O(1)-approximation algorithm for the Maximum Independent Set of Rectangles problem, and would thus solve a long-standing open problem. In practical applications, like the mentioned carpentry and many other settings, we can usually place the items freely that we want to cut out, which gives rise to the two-dimensional guillotine knapsack problem: Given a collection of axis-parallel rectangles without presumed coordinates, our goal is to place as many of them as possible in a square-shaped knapsack respecting the constraint that the placed objects can be separated by a sequence of guillotine cuts. Our main result for this problem is a quasi-PTAS, assuming the input data to be quasi-polynomially bounded integers. This factor matches the best known (quasi-polynomial time) result for (non-guillotine) two-dimensional knapsack.
A Novel method for automatic single molecule tracking of blinking molecules at low intensities
2013-05-07, Wöll, Dominik, Kölbl, Christoph, Stempfle, Beate Katharina, Karrenbauer, Andreas
Single molecule tracking provides unprecedented insights into diffusional processes of systems in life and material sciences. Determination of molecule positions with high accuracy and correct connection of the determined positions to tracks is a challenging task with, so far, no universal solution for single fluorescing molecules tackling the challenge of low signal-to-noise ratios, frequent blinking and photo bleaching. Thus, the development of novel algorithms for automatic single molecule fluorescence tracking is essential to analyse the huge amount of diffusional data obtained with single molecule widefield fluorescence microscopy. Here, we present a novel tracking model using a top-down polyhedral approach which can be implemented effectively using standard linear programming solvers. The results of our tracking approach are compared to the ground truth of simulated data with different diffusion coefficients, signal-to-noise ratios and particle densities. We also determine the dependency of blinking on the analysed distribution of diffusion coefficients. To confirm the functionality of our tracking method, the results of automatic tracking and manual tracking by a human expert are compared and discussed.
A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem
2016, Becker, Ruben, Fickert, Maximilian, Karrenbauer, Andreas
We present a novel algorithm for the min-cost flow problem that is competitive with recent third-party implementations of well-known algorithms for this problem and even outperforms them on certain realistic instances. We formally prove correctness of our algorithm and show that the worst-case running time is in O(‖b‖1(m + n log n)) where b is the vector of demands. Combined with standard scaling techniques, this pseudo-polynomial bound can be made polynomial in a straightforward way. Furthermore, we evaluate our approach experimentally. Our empirical findings indeed suggest that the running time does not significantly depend on the costs and that a linear dependence on ‖b‖1 is overly pessimistic.
Method, system and apparatus for power saving backlight
2014, Albrecht, Marc, Xu, Chihao, Karrenbauer, Andreas
A method, apparatus, and system for displaying an image on a liquid crystal display (LCD). The method, apparatus, and system can include condensing a plurality of pixel gray values to a concentrated pixel, the concentrated pixel assigned to a geometric position on a display and described by at least one of a plurality of parameters and gray value; forming the concentrated pixels to a condensed image; resolving a light spread function of a first LED in substantially the same resolution as the condensed image; calculating a backlight needed based on the condensed image; and optimizing a value of a plurality of LEDs by considering the contribution of the plurality of LEDs on the concentrated pixel, wherein light spread functions of the LEDs are used.
The interval constrained 3-coloring problem
2015-08, Byrka, Jaroslaw, Karrenbauer, Andreas, Sanità, Laura
In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-complete, if the number of colors is part of the input and that the problem is solvable in polynomial time, if the number of colors is at most 2. We also show that it is hard to satisfy almost all of the constraints for a feasible instance (even in the restricted case where each interval is used at most once). This implies APX-hardness of maximizing the number of simultaneously satisfiable intervals.
Improvements to keyboard optimization with integer programming
2014, Karrenbauer, Andreas, Oulasvirta, Antti
Keyboard optimization is concerned with the design of keyboards for different terminals, languages, user groups, and tasks. Previous work in HCI has used random search based methods, such as simulated annealing. These "black box" approaches are convenient, because good solutions are found quickly and no assumption must be made about the objective function. This paper contributes by developing integer programming (IP) as a complementary approach. To this end, we present IP formulations for the letter assignment problem and solve them by branch-and-bound. Although computationally expensive, we show that IP offers two strong benefits. First, its structured non-random search approach improves the out- comes. Second, it guarantees bounds, which increases the designer's confidence over the quality of results. We report improvements to three keyboard optimization cases.
Leveling the Grid
2013-12-18, Cornelsen, Sabine, Karrenbauer, Andreas, Li, Shujun
Motivated by an application in image processing, we introduce the grid-leveling problem. It turns out to be the dual of a minimum cost ow problem for an apex graph with a grid graph as its basis. We present an O(n3=2) algorithm for this problem. The optimum solution recovers missing DC coe cients from image and video coding by Discrete Cosine Transform used in popular standards like JPEG and MPEG. Generally, we prove that there is an O(n3=2) min-cost ow algorithm for networks that, after removing one node, are planar, have bounded degrees, and have bounded capacities. The costs may be arbitrary.