On the complexity of robust geometric programming with polyhedral uncertainty

Geometric Programming is a useful tool with a wide range of applications in engineering. As in real-world problems input data is likely to be affected by uncertainty, robust geometric programming has been introduced. It is an open question whether there exists a tractable reformulation of the robust geometric programming model. We provide a negative answer by showing that robust geometric programming with polyhedral uncertainty is co-NP hard, and provide positive results for the case of interval uncertainty.     

On computation complexity problems concerning relation algebras

In this paper, we study the computation complexity of some algebraic combinatorial problems that are closely associated with the graph isomorphism problem. The key point of our considerations is a relation algebra which is a combinatorial analog of a cellular algebra. We present upper bounds on the complexity of central algorithms for relation algebras such as finding the standard basis of extensions and intersection of relation algebras. Also, an approach is described to the graph isomorphism problem involving Schurian relation algebras (these algebras arise from the centralizing rings of permutation groups). We also discuss a number of open problems and possible directions for further investigation. Bibliography: 18 titles. Translated by I. N.Ponomarenko. Translated fromZapiski Nauchnykh Seminarov POMI, Vol 202, 1992, pp. 116–134.     

On the complexity of a class of combinatorial optimization problems with uncertainty

We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})² m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented uncertainty but is polynomially solvable in the case of the interval representation of uncertainty. Received: July 1998 / Accepted: May 2000?Published online March 22, 2001     

Computing the complexity of the relation of isometry between separable Banach spaces

We compute here the Borel complexity of the relation of isometry between separable Banach spaces, using results of Gao, Kechris [2], Mayer‐Wolf [5], and Weaver [8]. We show that this relation is Borel bireducible to the universal relation for Borel actions of Polish groups. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On 2-stage robust LP with RHS uncertainty: complexity results and applications

We investigate here the class—denoted R-LP-RHSU—of two-stage robust linear programming problems with right-hand-side uncertainty. Such problems arise in many applications e.g: robust PERT scheduling (with uncertain task durations); robust maximum flow (with uncertain arc capacities); robust network capacity expansion problems; robust inventory management; some robust production planning problems in the context of power production/distribution systems. It is shown that such problems can be formulated as large scale linear programs with associated nonconvex separation subproblem. A formal proof of strong NP-hardness for the general case is then provided, and polynomially solvable subclasses are exhibited. Differences with other previously described robust LP problems (featuring row-wise uncertainty instead of column wise uncertainty) are highlighted.     

On the relation between stability and contractivity

This paper concerns the rate of growth of numerical approximations obtained by one-step methods for solving linear stiff initial value problems. For some of these methods weak stability with respect to arbitrary norms is shown to be equivalent to contractivity. This kind of stability is also proved to entail a barrierp1 for the order of accuracyp within a broad class of methods, including general Runge-Kutta methods withm1 stages.Dedicated to Professor Germund Dahlquist on the occasion of his sixtieth birthday.     

Generalized energy-time uncertainty relation

Starting with the Schrödinger universal uncertainty relations for arbitrary observables, we propose a generalization of the time uncertainty concept introduced by Mandelshtam and Tamm making it invariant with respect to the choice of observables and free of singularities. We show that for coherent states, the quantity introduced can be interpreted as the variance of the inverse effective frequency of the microsystem. This allows treating the generalized energy-time uncertainty relations similarly to the energy-inverse temperature uncertainty relations in statistical thermodynamics.     

On the relation between cluster and classical tilting

Let be a triangulated category with a cluster tilting subcategory U. The quotient category is abelian; suppose that it has finite global dimension.We show that projection from to sends cluster tilting subcategories of to support tilting subcategories of , and that, in turn, support tilting subcategories of can be lifted uniquely to weak cluster tilting subcategories of .     

On the relation between two Minkowski functions

The definition of Minkowski's “Fragefunktion”? (x) is recapitulated. This function is compared to a function L(x) introduced by the author in 1926. It is shown that the inverse function P(w) = x to the function L(x) is related to the Fragefunktion through ?(w) = P(w)?1.     

On relationships between complexity classes of Turing machines

Classes of time and space complexity of Turing machines are defined, and relationships between them are discussed. New relationships between the defined complexity classes are described.     

On a relation between the Sylow and Baer-Suzuki theorems

Given a set π of primes, say that a finite group G satisfies the Sylow π-theorem if every two maximal π-subgroups of G are conjugate; equivalently, the full analog of the Sylow theorem holds for π-subgroups. Say also that a finite group G satisfies the Baer-Suzuki π-theorem if every conjugacy class of G every pair of whose elements generate a π-subgroup itself generates a π-subgroup. In this article we prove, using the classification of finite simple groups, that if a finite group satisfies the Sylow π-theorem then it satisfies the Baer-Suzuki π-theorem as well.     

On the relation between the A-polynomial and the Jones polynomial

This paper shows that the noncommutative generalization of the A-polynomial of a knot, defined using Kauffman bracket skein modules, together with finitely many colored Jones polynomials, determines the remaining colored Jones polynomials of the knot. It also shows that under certain conditions, satisfied for example by the unknot and the trefoil knot, the noncommutative generalization of the A-polynomial determines all colored Jones polynomials of the knot.

     

On the relation between an operator and its self-commutator

We show that a bounded operator A on a Hilbert space belongs to a certain set associated with its self-commutator [A^?,A], provided that A−zI can be approximated by invertible operators for all complex numbers z. The theorem remains valid in a general C^?-algebra of real rank zero under the assumption that A−zI belong to the closure of the connected component of unity in the set of invertible elements. This result implies the Brown-Douglas-Fillmore theorem and Huaxin Lin?s theorem on almost commuting matrices. Moreover, it allows us to refine the former and to extend the latter to operators of infinite rank and other norms (including the Schatten norms on the space of matrices). The proof is based on an abstract theorem, which states that a normal element of a C^?-algebra of real rank zero satisfying the above condition has a resolution of the identity associated with any open cover of its spectrum.     

On the relation between topological entropy and entropy dimension

Mathematical Notes - For the Lipschitz mapping of a metric compact set into itself, there is a classical upper bound on topological entropy, namely, the product of the entropy dimension of the...     

Metric adjusted skew information and uncertainty relation

We show that an uncertainty relation for Wigner-Yanase-Dyson skew information proved by Yanagi (2010) [10] can hold for an arbitrary quantum Fisher information under some conditions. This is a refinement of the result of Gibilisco and Isola (2011) [4].     

On the relation between the singular and the weak coupling limits

After having recalled some definitions concerning quantum stochastic processes and, in particular, quantum Brownian motions, a general scheme is introduced which allows a unified approach to the weak coupling and singular coupling limits. The analogies and differences between the two are discussed. The main difference consists of the fact that, in the singular coupling limit, the use of a Hamiltonian unbounded below seems to be unavoidable, while this is not the case for the weak coupling limit.     

On a relation between four line-segments

Summary A symmetrical relation between four line-segments is defined which is a generalization of an elementary one for three segments. A tetrahedron A=(A₁A₂A₃A₄) being given the locus F of the points P for which PA_i satisfy the relation is shown to be a cyclide. F is the envelope of the set of spheres orthogonal to the circumsphere of A and whith their centres on the Steiner ellipsoid of A. Properties of F are discussed for special types of tetrahedra. If A is a square the surface F is a torus. In memory of Guido Castelnuovo, in the recurrence of the first centenary of his birth.