In this article, we study the problem of enumerating the models of DNF formulas. The aim is to provide enumeration algorithms with a delay that depends polynomially on the size of each model and not on the size of the formula, which can be exponentially larger. We succeed for two subclasses of DNF formulas: we provide a constant delay algorithm for...
A crucial role of container shipping is maximizing container uptake onto vessels, optimizing the efficiency of a fundamental part of the global supply chain. In practice, liner shipping companies include block stowage patterns that ensure that containers in above and below deck partitions of bays have the same destination. Despite preventing restow...
We first show a simple but striking result in bilevel optimization: unconstrained $C^\infty$ smooth bilevel programming is as hard as general extended-real-valued lower semicontinuous minimization. We then proceed to a worst-case analysis of box-constrained bilevel polynomial optimization. We show in particular that any extended-real-valued semi-al...
Non-convex minimization problems are universally considered hard, and even guaranteeing that a computed solution is locally minimizing is known to be NP-hard. In this general context, our paper focuses on the problem of finding stationary points that satisfy an approximate second-order optimality condition, which serves to exclude strict saddles an...
It was previously shown by the authors that a directed graph on a linearly ordered set of edges (ordered graph) with adjacent unique source and sink (bipolar digraph) has a unique fully optimal spanning tree, that satisfies a simple criterion on fundamental cycle/cocycle directions. This result is related to a strengthening of the notion of optimal...
Existing computational game theory studies consider compact representations of games that capture agent interaction in real-world environments and examine computation aspects of computing equilibrium concepts to analyze or predict agent behavior. One of the most well-studied representations that capture many commonly studied real-world environments...
The Riemann hypothesis and the $P$ versus $NP$ problem are two of the most important unsolved Millennium Prize Problems. Let $\Psi(n) = n \cdot \prod_{q \mid n} \left(1 + \frac{1}{q} \right)$ denote the Dedekind $\Psi$ function where $q \mid n$ means the prime $q$ divides $n$. Define, for $n \geq 3$; the ratio $R(n) = \frac{\Psi(n)}{n \cdot \log \l...
A monitoring edge-geodetic set, or simply an MEG-set, of a graph G is a vertex subset M ⊆ V (G) such that given any edge e of G, e lies on every shortest u-v path of G, for some u, v ∈ M. The monitoring edge-geodetic number of G, denoted by meg(G), is the minimum cardinality of such an MEG-set. This notion provides a graph theoretic model of the ne...
The formal analysis of cryptographic protocols traditionally focuses on trace and equivalence properties, for which decision procedures in the symbolic (or Dolev-Yao, or DY) model are known. However, many relevant security properties are expressed as DY hyperproperties that involve quantifications over both execution paths and attacker computations...
In the field of distributed computing by robot swarms, the research comprehends manifold models where robots operate in the Euclidean plane through a sequence of look-compute-move cycles. Models under study differ for (i) the possibility of storing constant-size information, (ii) the possibility of communicating constant-size information, and (iii)...
