Robust combinatorial optimization with variable cost uncertainty

We present in this paper a new model for robust combinatorial optimization with cost uncertainty that generalizes the classical budgeted uncertainty set. We suppose here that the budget of uncertainty is given by a function of the problem variables, yielding an uncertainty multifunction. The new model is less conservative than the classical model and approximates better Value-at-Risk objective functions, especially for vectors with few non-zero components. An example of budget function is constructed from the probabilistic bounds computed by Bertsimas and Sim. We provide an asymptotically tight bound for the cost reduction obtained with the new model. We turn then to the tractability of the resulting optimization problems. We show that when the budget function is affine, the resulting optimization problems can be solved by solving n+1$n+1$ deterministic problems. We propose combinatorial algorithms to handle problems with more general budget functions. We also adapt existing dynamic programming algorithms to solve faster the robust counterparts of optimization problems, which can be applied both to the traditional budgeted uncertainty model and to our new model. We evaluate numerically the reduction in the price of robustness obtained with the new model on the shortest path problem and on a survivable network design problem.     

Solving the stochastic steady-state diffusion problem using multigrid

Darran Furnival ^{We study multigrid for solving the stochastic steady-state diffusionproblem. We operate under the mild assumption that the diffusioncoefficient takes the form of a finite Karhunen-Loèveexpansion. The problem is discretized using a finite-elementmethodology using the polynomial chaos method to discretizethe stochastic part of the problem. We apply a multigrid algorithmto the stochastic problem in which the spatial discretizationis varied from grid to grid while the stochastic discretizationis held constant. We then show, theoretically and experimentally,that the convergence rate is independent of the spatial discretization,as in the deterministic case, and the stochastic discretization.}     

Shellable graphs and sequentially Cohen-Macaulay bipartite graphs

Associated to a simple undirected graph G is a simplicial complex ΔG whose faces correspond to the independent sets of G. We call a graph G shellable if ΔG is a shellable simplicial complex in the non-pure sense of Björner-Wachs. We are then interested in determining what families of graphs have the property that G is shellable. We show that all chordal graphs are shellable. Furthermore, we classify all the shellable bipartite graphs; they are precisely the sequentially Cohen-Macaulay bipartite graphs. We also give a recursive procedure to verify if a bipartite graph is shellable. Because shellable implies that the associated Stanley-Reisner ring is sequentially Cohen-Macaulay, our results complement and extend recent work on the problem of determining when the edge ideal of a graph is (sequentially) Cohen-Macaulay. We also give a new proof for a result of Faridi on the sequentially Cohen-Macaulayness of simplicial forests.     

Schrödinger Uncertainty Relations and Physical Features of Correlated-Coherent States

We show that the difference between the Schrödinger uncertainty relations (UR) and the Heisenberg UR is fundamental. We propose a modified version of stochastic mechanics that allows clearly demonstrating that the contributions from the anticommutator and the commutator to the Schrödinger UR are equally important. A classification of quantum states minimizing the Schrödinger UR at an arbitrary instant is proposed. We show that the correlation of the coordinate and momentum fluctuations in such correlated-coherent states (CCS) is largely determined by the contributions from not only the commutator but also the anticommutator of the corresponding operators. We demonstrate that the character of this correlation changes qualitatively in time from the antiphase correlation typical for the Heisenberg UR to the inphase correlation for which the contribution from the anticommutator is decisive. We comparatively analyze properties of a free microparticle and a quantum oscillator in CCS and show that the CCS correspond to traveling-standing de Broglie waves in both models.     

Fragmented deformations of primitive multiple curves

A primitive multiple curve is a Cohen-Macaulay irreducible projective curve Y that can be locally embedded in a smooth surface, and such that Y _red is smooth. We study the deformations of Y to curves with smooth irreducible components, when the number of components is maximal (it is then the multiplicity n of Y). We are particularly interested in deformations to n disjoint smooth irreducible components, which are called fragmented deformations. We describe them completely. We give also a characterization of primitive multiple curves having a fragmented deformation.     

Efficiency in the trust game: an experimental study of precommitment

We experimentally test a precommitment mechanism for the trust game. Before the investor’s decision, the allocator places an amount into escrow, to be forfeited if he keeps the proceeds of investment for himself. We vary the available escrow amounts—in particular, whether there is a high amount that gives rise to an efficient equilibrium—and whether escrow is voluntary or imposed. We find that when chosen, the high escrow amount does lead to efficient outcomes. We also find substantial investment when the high amount is unavailable or not chosen, though well below that when it is chosen, and declining over time. We find only weak evidence for behavioral theories, such as crowding out and signaling. These results are seen when escrow choices are imposed as well as when they are voluntary.      

New Models of the Generalized Minimum Spanning Tree Problem

We consider a generalization of the Minimum Spanning Tree Problem, called the Generalized Minimum Spanning Tree Problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present a stronger result regarding its complexity, namely, the GMST problem is NP-hard even on trees as well an exact exponential time algorithm for the problem based on dynamic programming. We describe new mixed integer programming models of the GMST problem, mainly containing a polynomial number of constraints. We establish relationships between the polytopes corresponding to their linear relaxations. Based on a new model of the GMST we present a solution procedure that solves the problem to optimality for graphs with nodes up to 240. We discuss the advantages of our method in comparison with earlier methods.     

On Lebesgue-type inequalities for greedy approximation

We study the efficiency of greedy algorithms with regard to redundant dictionaries in Hilbert spaces. We obtain upper estimates for the errors of the Pure Greedy Algorithm and the Orthogonal Greedy Algorithm in terms of the best m-term approximations. We call such estimates the Lebesgue-type inequalities. We prove the Lebesgue-type inequalities for dictionaries with special structure. We assume that the dictionary has a property of mutual incoherence (the coherence parameter of the dictionary is small). We develop a new technique that, in particular, allowed us to get rid of an extra factor m^1/2 in the Lebesgue-type inequality for the Orthogonal Greedy Algorithm.     

Some problems of the theory of quantum statistical systems with an energy spectrum of the fractional-power type

We consider the problem of the effective interaction potential in a quantum many-particle system leading to the fractional-power dispersion law. We show that passing to fractional-order derivatives is equivalent to introducing a pair interparticle potential. We consider the case of a degenerate electron gas. Using the van der Waals equation, we study the equation of state for systems with a fractional-power spectrum. We obtain a relation between the van der Waals constant and the phenomenological parameter ??, the fractional-derivative order. We obtain a relation between energy, pressure, and volume for such systems: the coefficient of the thermal energy is a simple function of ??. We consider Bose??Einstein condensation in a system with a fractional-power spectrum. The critical condensation temperature for 1 < ?? < 2 is greater in the case under consideration than in the case of an ideal system, where ?? = 2.     

Weights in the cohomology of toric varieties

We describe the weight filtration in the cohomology of toric varieties. We present a role of the Frobenius automorphism in an elementary way. We prove that equivariant intersection homology of an arbitrary toric variety is pure. We obtain results concerning Koszul duality: nonequivariant intersection cohomology is equal to the cohomology of the Koszul complexIH _T ^* (X)⊗H*(T). We also describe the weight filtration inIH ^*(X). Supported by KBN 2P03A 00218 grant. I thank, Institute of Mathematics, Polish Academy of Science for hospitality.     

Friedman-reflexivity

In the present paper, we explore an idea of Harvey Friedman to obtain a coordinate-free presentation of consistency. For some range of theories, Friedman's idea delivers actual consistency statements (modulo provable equivalence). For a wider range, it delivers consistency-like statements.We say that a sentence C is an interpreter of a finitely axiomatised A over U iff it is the weakest statement C over U, with respect to U-provability, such that $U+C$ interprets A. A theory U is Friedman-reflexive iff every finitely axiomatised A has an interpreter over U. Friedman shows that Peano Arithmetic, PA, is Friedman-reflexive.We study the question which theories are Friedman-reflexive. We show that a very weak theory, Peano Corto, is Friedman-reflexive. We do not get the usual consistency statements here, but bounded, cut-free, or Herbrand consistency statements. We illustrate that Peano Corto as a base theory has additional desirable properties.We prove a characterisation theorem for the Friedman-reflexivity of sequential theories. We provide an example of a Friedman-reflexive sequential theory that substantially differs from the paradigm cases of Peano Arithmetic and Peano Corto.Interpreters over a Friedman-reflexive U can be used to define a provability-like notion for any finitely axiomatised A that interprets U. We explore what modal logics this idea gives rise to. We call such logics interpreter logics. We show that, generally, these logics satisfy the Löb Conditions, aka K4. We provide conditions for when interpreter logics extend S4, K45, and Löb's Logic. We show that, if either U or A is sequential, then the condition for extending Löb's Logic is fulfilled. Moreover, if our base theory U is sequential and if, in addition, its interpreters can be effectively found, we prove Solovay's Theorem. This holds even if the provability-like operator is not necessarily representable by a predicate of Gödel numbers.At the end of the paper, we briefly discuss how successful the coordinate-free approach is.     

The complexity of a cyclic scheduling problem with identical machines and precedence constraints

We consider a set T of tasks with unit processing times. Each of them must be executed infinitely often. A uniform constraint is defined between two tasks and induces a set of precedence constraints on their successive executions. We limit our study to a subset of uniform constraints corresponding to two hypotheses often verified in practice: Each execution of T must end by a special task f, and uniform constraints between executions from different iterations start from f. We have a fixed number of identical machines. The problem is to find a periodic schedule of T which maximizes the throughput. We prove that this problem is NP-hard and show that it is polynomial for two machines. We also present another nontrivial polynomial subcase which is a restriction of uniform precedence constraints.     

The Bi-Hamiltonian Theory of the Harry Dym Equation

We describe how the Harry Dym equation fits into the the bi-Hamiltonian formalism for the Korteweg–de Vries equation and other soliton equations. This is achieved using a certain Poisson pencil constructed from two compatible Poisson structures. We obtain an analogue of the Kadomtsev–Petviashivili hierarchy whose reduction leads to the Harry Dym hierarchy. We call such a system the HD–KP hierarchy. We then construct an infinite system of ordinary differential equations (in infinitely many variables) that is equivalent to the HD–KP hierarchy. Its role is analogous to the role of the Central System in the Kadomtsev–Petviashivili hierarchy.     

A variational problem with lack of compactness for H(S;S) maps of prescribed degree

We consider, for maps in H^1/2(S¹;S¹), a family of (semi)norms equivalent to the standard one. We ask whether, for such a norm, there is some map in H^1/2(S¹;S¹) of prescribed topological degree equal to 1 and minimal norm. In general, the answer is no, due to concentration phenomena. The existence of a minimal map is sensitive to small perturbations of the norm. We derive a sufficient condition for the existence of minimal maps. In particular, we prove that, for every given norm, there are arbitrarily small perturbations of it for which the minimum is attained. In case there is no minimizer, we determine the asymptotic behavior of minimizing sequences. We prove that, for such minimizing sequences, the energy concentrates near a point of S¹. We describe this concentration in terms of bubbling-off of circles.     

On the analysis of optimization problems in arc-dependent networks

This paper is concerned with the design and analysis of algorithms for optimization problems in arc-dependent networks. A network is said to be arc-dependent if the cost of an arc $a$ depends upon the arc taken to enter $a$. These networks are fundamentally different from traditional networks in which the cost associated with an arc is a fixed constant and part of the input. We first study the arc-dependent shortest path (ADSP) problem, which is also known as the suffix-1 path-dependent shortest path problem in the literature. This problem has a polynomial time solution if the shortest paths are not required to be simple. The ADSP problem finds applications in a number of domains, including highway engineering, turn penalties and prohibitions, and fare rebates. In this paper, we are interested in the ADSP problem when restricted to simple paths. We call this restricted version the simple arc-dependent shortest path (SADSP) problem. We show that the SADSP problem is NP-complete. We present inapproximability results and an exact exponential algorithm for this problem. We also extend our results for the longest path problem in arc-dependent networks. Additionally, we explore the problem of detecting negative cycles in arc-dependent networks and discuss its computational complexity. Our results include variants of the negative cycle detection problem such as longest, shortest, heaviest, and lightest negative simple cycles.²     

Rigorous Formulation of a 2D Conformal Model in the Fock–Krein Space: Construction of the Global Op J *-Algebra of Fields and Currents

We use the formalism of the 2D massless scalar field model in an indefinite space of the Fock–Krein type as a basis for constructing a rigorous formulation of 2D quantum conformal theories. We show that the sought construction is a several-stage procedure whose central block is the construction of a new type of representation of the Virasoro algebra. We develop the first stage of this procedure, which is to construct a special global algebra of fields and currents generated by exponential generators. We obtain a system of commutation relations for the Wick-squared currents used in the definition of the Virasoro generators. We prove the existence of Wick exponentials of the current given by operator-valued generalized functions; the sought global algebra is rigorously defined as the algebra of current and field, Wick and normal exponentials on a common dense invariant domain in a Fock–Krein space.     

When does the Haver property imply selective screenability?

We point out that in metric spaces Haver's property is not equivalent to the property introduced by Addis and Gresham. We prove that they are equal when the space has the Hurewicz property. We prove several results about the preservation of Haver's property in products. We show that if a separable metric space has the Haver property, and the nth power has the Hurewicz property, then the nth power has the Addis-Gresham property. R. Pol showed earlier that this is not the case when the Hurewicz property is replaced by the weaker Menger property. We introduce new classes of weakly infinite dimensional spaces.     

Sorting weighted distances with applications to objective function evaluations in single facility location problems

We consider single facility location problems defined on rectilinear spaces and spaces induced by tree networks. We focus on discrete cases, where the facility is restricted to be in a prespecified finite set S, and the goal is to evaluate the objective at each point in S. We present efficient improved algorithms to perform this task for several classes of objective functions.     

Moser iteration for (quasi)minimizers on metric spaces

We study regularity properties of quasiminimizers of the p-Dirichlet integral on metric measure spaces. We adapt the Moser iteration technique to this setting and show that it can be applied without an underlying differential equation. However, we have been able to run the Moser iteration fully only for minimizers. We prove Caccioppoli inequalities and local boundedness properties for quasisub- and quasisuperminimizers. This is done in metric spaces equipped with a doubling measure and supporting a weak (1, p)-Poincaré inequality. The metric space is not required to be complete. We also provide an example which shows that the dilation constant from the weak Poincaré inequality is essential in the condition on the balls in the Harnack inequality. This fact seems to have been overlooked in the earlier literature on nonlinear potential theory on metric spaces.     

Partial Decomposition Bases and Warfield Modules

We consider the class of ?_p -modules with partial decomposition bases. This class was developed in order to extend Barwise and Eklof's classification of torsion groups in L _∞ω to Warfield modules. We prove that this class is the natural generalization of Warfield modules in L _∞ω, is strictly larger than the class of Warfield modules, and in fact strictly larger than the class of modules partially isomorphic to Warfield modules. We prove that this class is identical to the class of k-modules of Hill and Megibben, and, as such, closed under direct summands.