A subexponential bound for linear programming

We present a simple randomized algorithm which solves linear programs withn constraints andd variables in expected $$\min \{ O(d^2 2^d n),e^{2\sqrt {dIn({n \mathord{\left/ {\vphantom {n {\sqrt d }}} \right. \kern-\nulldelimiterspace} {\sqrt d }})} + O(\sqrt d + Inn)} \}$$ time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input); to be precise, the algorithm computes the lexicographically smallest nonnegative point satisfyingn given linear inequalities ind variables. The expectation is over the internal randomizations performed by the algorithm, and holds for any input. In conjunction with Clarkson's linear programming algorithm, this gives an expected bound of $$O(d^2 n + e^{O(\sqrt {dInd} )} ).$$ The algorithm is presented in an abstract framework, which facilitates its application to several other related problems like computing the smallest enclosing ball (smallest volume enclosing ellipsoid) ofn points ind-space, computing the distance of twon-vertex (orn-facet) polytopes ind-space, and others. The subexponential running time can also be established for some of these problems (this relies on some recent results due to Gärtner).     

Multiple spatial sounds in hierarchical menu navigation for visually impaired computer users

This paper describes a user study on the benefits and drawbacks of simultaneous spatial sounds in auditory interfaces for visually impaired and blind computer users. Two different auditory interfaces in spatial and non-spatial condition were proposed to represent the hierarchical menu structure of a simple word processing application. In the horizontal interface, the sound sources or the menu items were located in the horizontal plane on a virtual ring surrounding the user’s head, while the sound sources in the vertical interface were aligned one above the other in front of the user. In the vertical interface, the central pitch of the sound sources at different elevations was changed in order to improve the otherwise relatively low localization performance in the vertical dimension. The interaction with the interfaces was based on a standard computer keyboard for input and a pair of studio headphones for output. Twelve blind or visually impaired test subjects were asked to perform ten different word processing tasks within four experiment conditions. Task completion times, navigation performance, overall satisfaction and cognitive workload were evaluated. The initial hypothesis, i.e. that the spatial auditory interfaces with multiple simultaneous sounds should prove to be faster and more efficient than non-spatial ones, was not confirmed. On the contrary—spatial auditory interfaces proved to be significantly slower due to the high cognitive workload and temporal demand. The majority of users did in fact finish tasks with less navigation and key pressing; however, they required much more time. They reported the spatial auditory interfaces to be hard to use for a longer period of time due to the high temporal and mental demand, especially with regards to the comprehension of multiple simultaneous sounds. The comparison between the horizontal and vertical interface showed no significant differences between the two. It is important to point out that all participants were novice users of the system; therefore it is possible that the overall performance could change with a more extensive use of the interfaces and an increased number of trials or experiments sets. Our interviews with visually impaired and blind computer users showed that they are used to sharing their auditory channel in order to perform multiple simultaneous tasks such as listening to the radio, talking to somebody, using the computer, etc. As the perception of multiple simultaneous sounds requires the entire capacity of the auditory channel and total concentration of the listener, it does therefore not enable such multitasking.     

Multi-scale computational model for failure analysis of metal frames that includes softening and local buckling

In this work we present a new modelling paradigm for computing the complete failure of metal frames by combining the stress-resultant beam model and the shell model. The shell model is used to compute the material parameters that are needed by an inelastic stress-resultant beam model; therefore, we consider the shell model as the meso-scale model and the beam model as the macro-scale model. The shell model takes into account elastoplasticity with strain-hardening and strain-softening, as well as geometrical nonlinearity (including local buckling of a part of a beam). By using results of the shell model, the stress-resultant inelastic beam model is derived that takes into account elastoplasticity with hardening, as well as softening effects (of material and geometric type). The beam softening effects are numerically modelled in a localized failure point by using beam finite element with embedded discontinuity. The original feature of the proposed multi-scale (i.e. shell-beam) computational model is its ability to incorporate both material and geometrical instability contributions into the stress-resultant beam model softening response. Several representative numerical simulations are presented to illustrate a very satisfying performance of the proposed approach.     

Computing median and antimedian sets in median graphs

The median (antimedian) set of a profile π=(u ₁,…,u _k ) of vertices of a graph G is the set of vertices x that minimize (maximize) the remoteness ∑ _i d(x,u _i ). Two algorithms for median graphs G of complexity O(n idim(G)) are designed, where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other algorithm which in addition computes antimedian sets and remoteness functions and works in all partial cubes.     

Left-forbidding cooperating distributed grammar systems

A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.     

Multi-view Superpixel Stereo in Urban Environments

Urban environments possess many regularities which can be efficiently exploited for 3D dense reconstruction from multiple widely separated views. We present an approach utilizing properties of piecewise planarity and restricted number of plane orientations to suppress reconstruction and matching ambiguities causing failures of standard dense stereo methods. We formulate the problem of the 3D reconstruction in MRF framework built on an image pre-segmented into superpixels. Using this representation, we propose novel photometric and superpixel boundary consistency terms explicitly derived from superpixels and show that they overcome many difficulties of standard pixel-based formulations and handle favorably problematic scenarios containing many repetitive structures and no or low textured regions. We demonstrate our approach on several wide-baseline scenes demonstrating superior performance compared to previously proposed methods.     

The <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>-Optimality of the IIPG Method for Odd Degrees of Polynomial Approximation in 1D

The paper deals with a numerical analysis of the incomplete interior penalty Galerkin (IIPG) method applied to one dimensional Poisson problem. Based on a particular choice of the interior penalty parameter σ (order of O(h ⁻¹)), we derive the optimal error estimate in the L ²-norm for odd degrees of polynomial approximation for locally quasi-uniform meshes. Moreover, we show that only the mentioned choice of the penalty parameter leads to optimal orders of convergence. Finally, presented numerical experiments verify the theoretical results.