Andreas Karrenbauer

Ruben Becker, Andreas Karrenbauer, Kurt Mehlhorn

We present an interior point method for the min-cost flow problem that uses arc contractions and deletions to steer clear from the boundary of the polytope when path-following methods come too close. We obtain a randomized algorithm running in expected $\tilde O( m^{3/2} )$ time that only visits integer lattice points in the vicinity of the central path of the polytope. This enables us to use integer arithmetic like classical combinatorial algorithms typically do. We provide explicit bounds on the size of the numbers that appear during all computations. By presenting an integer arithmetic interior point algorithm we avoid the tediousness of floating point error analysis and achieve a method that is guaranteed to be free of any numerical issues. We thereby eliminate one of the drawbacks of numerical methods in contrast to combinatorial min-cost flow algorithms that still yield the most efficient implementations in practice, despite their inferior worst-case time complexity.

Vincenzo Bonifaci, Enrico Facca, Frederic Folz et al.

In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks. For the shortest path problem, a mathematical model for the evolution of the slime is available and it has been shown in computer experiments and through mathematical analysis that the dynamics solves the shortest path problem. In this paper, we introduce a dynamics for the network design problem. We formulate network design as the problem of constructing a network that efficiently supports a multi-commodity flow problem. We investigate the dynamics in computer simulations and analytically. The simulations show that the dynamics is able to construct efficient and elegant networks. In the theoretical part we show that the dynamics minimizes an objective combining the cost of the network and the cost of routing the demands through the network. We also give alternative characterization of the optimum solution.

Niraj Ramesh Dayama, Morteza Shiripour, Antti Oulasvirta et al.

Computational design of menu systems has been solved in limited cases such as the linear menu (list) as an assignment task, where commands are assigned to menu positions while optimizing for for users selection performance and distance of associated items. We show that this approach falls short with larger, hierarchically organized menu systems, where one must also take into account how users navigate hierarchical structures. This paper presents a novel integer programming formulation that models hierarchical menus as a combination of the exact set covering problem and the assignment problem. It organizes commands into ordered groups of ordered groups via a novel objective function based on information foraging theory. It minimizes, on the one hand, the time required to select a command whose location is known from previous usage and, on the other, the time wasted in irrelevant parts of the menu while searching for commands whose location is not known. The convergence of these two factors yields usable, well-ordered command hierarchies from a single model. In generated menus, the lead (first) elements of a group or tab are good indicators of the remaining contents, thereby facilitating the search process. In a controlled usability evaluation, the performance of computationally designed menus was 25 faster than existing commercial designs with respect to selection time. The algorithm is efficient for large, representative instances of the problem. We further show applications in personalization and adaptation of menu systems.

Shujun Li, Andreas Karrenbauer, Dietmar Saupe et al.

A general method for recovering missing DCT coefficients in DCT-transformed images is presented in this work. We model the DCT coefficients recovery problem as an optimization problem and recover all missing DCT coefficients via linear programming. The visual quality of the recovered image gradually decreases as the number of missing DCT coefficients increases. For some images, the quality is surprisingly good even when more than 10 most significant DCT coefficients are missing. When only the DC coefficient is missing, the proposed algorithm outperforms existing methods according to experimental results conducted on 200 test images. The proposed recovery method can be used for cryptanalysis of DCT based selective encryption schemes and other applications.