### A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

We give a complete characterization of the class of functions that are the intensional behaviours of primitive recursive (PR) algorithms. This class is the set of primitive recursive functions that have a null basic case of recursion. This result is obtained using the property of ultimate unarity and a geometrical approach of sequential functions on N the set of positive integers.

We characterize the class [...] L32 ${L}_{3}^{2}$ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 ${L}_{3}^{2}$ in the class of threshold graphs, where n is the number of vertices of a tested graph.

A lower bound for the number of comparisons is obtained, required by a computational problem of classification of an arbitrarily chosen point of the Euclidean space with respect to a given finite family of polyhedral (non-convex, in general) sets, covering the space. This lower bound depends, roughly speaking, on the minimum number of convex parts, into which one can decompose these polyhedral sets. The lower bound is then applied to the knapsack problem.

We propose a modified standard embedding for solving the linear complementarity problem (LCP). This embedding is a special one-parametric optimization problem $P\left(t\right),t\in [0,1]$. Under the conditions (A3) (the Mangasarian–Fromovitz Constraint Qualification is satisfied for the feasible set $M\left(t\right)$ depending on the parameter $t$), (A4) ($P\left(t\right)$ is Jongen–Jonker– Twilt regular) and two technical assumptions, (A1) and (A2), there exists a path in the set of stationary points connecting the chosen starting point for $P\left(0\right)$ with a certain...