A faster algorithm for the continuous bilevel knapsack problem

We construct a fast algorithm with time complexity $O(nlogn)$ for a continuous bilevel knapsack problem with interdiction constraints for $n$ items. This improves on a recent algorithm from the literature with quadratic time complexity $O\left(n^2\right)$.     

Edge decompositions and rooted packings of graphs

Let H be a fixed graph. In this paper we consider the problem of edge decomposition of a graph into subgraphs isomorphic to H or $2K_2$ (a 2-edge matching). We give a partial classification of the problems of existence of such decomposition according to the computational complexity. More specifically, for some large class of graphs H we show that this problem is polynomial time solvable and for some other large class of graphs it is NP-complete. These results can be viewed as some edge decomposition analogs of a result by Loebl and Poljak who classified according to the computational complexity the problem of existence of a graph factor with components isomorphic to H or $K_2$. In the proofs of our results we apply so-called rooted packings into graphs which are mutual generalizations of both edge decompositions and factors of graphs.     

The Frobenius complexity of Hibi rings

We study the Frobenius complexity of Hibi rings over fields of characteristic $p>0$. In particular, for a certain class of Hibi rings (which we call ${\omega }^{(?1)}$-level), we compute the limit of the Frobenius complexity as $p\to \infty$.     

A geometric way to build strong mixed-integer programming formulations

We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an $r$-dimensional linear space. The resulting MIP formulation is ideal, and uses exactly $r$ integer variables and $2\times \left(\#\text{of spanning hyperplanes}\right)$ general inequality constraints. We use this result to derive novel logarithmic-sized ideal MIP formulations for discontinuous piecewise linear functions and structures appearing in robotics and power systems problems.     

On the linear extension complexity of stable set polytopes for perfect graphs

We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-joins and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behavior of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph $G$ depending linearly on the size of $G$ and involving the depth of a decomposition tree of $G$ in terms of basic perfect graphs.     

The complexity of computing a robust flow

The Maximum Robust Flow problem asks for a flow on the paths of a network maximizing the guaranteed amount of flow surviving the removal of any $k$ arcs. We point out a flaw in a previous publication that claimed $NP$-hardness for this problem when $k=2$. For the case that $k$ is part of the input, we present a new hardness proof. We also discuss the complexity of the integral version of the problem.     

Discrete Lagrange problems with constraints valued in a Lie group

The Lagrange problem is established in the discrete field theory subject to constraints with values in a Lie group. For the admissible sections that satisfy a certain regularity condition, we prove that the critical sections of such problems are the solutions of a canonically unconstrained variational problem associated with the Lagrange problem (discrete Lagrange multiplier rule). This variational problem has a discrete Cartan 1-form, from which a Noether theory of symmetries and a multisymplectic form formula are established. The whole theory is applied to the Euler-Poincaré reduction in the discrete field theory, concluding as an illustration with the remarkable example of the harmonic maps of the discrete plane in the Lie group $SO(n)$.     

Representation of asymptotic values for nonexpansive stochastic control systems

In ergodic stochastic problems the limit of the value function $V_{\lambda }$ of the associated discounted cost functional with infinite time horizon is studied, when the discounted factor $\lambda$ tends to zero. These problems have been well studied in the literature and the used assumptions guarantee that the value function $\lambda V_{\lambda }$ converges uniformly to a constant as $\lambda \to 0$. The objective of this work consists in studying these problems under the assumption, namely, the nonexpansivity assumption, under which the limit function is not necessarily constant. Our discussion goes beyond the case of the stochastic control problem with infinite time horizon and discusses also $V_{\lambda }$ given by a Hamilton–Jacobi–Bellman equation of second order which is not necessarily associated with a stochastic control problem. On the other hand, the stochastic control case generalizes considerably earlier works by considering cost functionals defined through a backward stochastic differential equation with infinite time horizon and we give an explicit representation formula for the limit of $\lambda V_{\lambda }$, as $\lambda \to 0$.     

Expected reliability of communication protocols

We consider the problem of sending a message from a sender $s$ to a receiver $r$ through an unreliable network by specifying in a protocol what each vertex is supposed to do if it receives the message from one of its neighbors. A protocol for routing a message in such a graph is finite if it never floods $r$ with an infinite number of copies of the message. The expected reliability of a given protocol is the probability that a message sent from $s$ reaches $r$ when the edges of the network fail independently with probability $1?p$.We discuss, for given networks, the properties of finite protocols with maximum expected reliability in the case when $p$ is close to 0 or 1, and we describe networks for which no one protocol is optimal for all values of $p$. In general, finding an optimal protocol for a given network and fixed probability is challenging and many open problems remain.