Borsuk’s Partition Problem in $$(\mathbb{R}^{n},\ell_{p})$$

Mathematical Notes - For a bounded set $$X$$ with diameter $$d_{C}(X)$$ in a finite-dimensional normed space with an origin-symmetric convex body $$C$$ as the unit ball, the Borsuk number of $$X$$...     

On the Borsuk and Erdös—Hadwiger numbers

Two classical problems of combinatorial geometry, the Borsuk problem about splitting sets into parts of smaller diameter and the Erdös—Hadwiger problem about coloring Euclidean space, are studied. New asymptotic estimates are obtained for the quantities f(d) (the minimal number of parts of smaller diameter into which any bounded set in ?^d can be decomposed) and χ(?^d) (the minimal number of colors required to color all points ?^d so that any points at distance 1 from each other have different colors), which are the main objects of study in these problems.     

An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems

In this paper a local integral simplex algorithm will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex algorithm creates and solves the problems in a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc. The solution to at least one of these subproblems is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is an optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n.A method for programming the algorithms in this paper to run on parallel computers is discussed briefly.     

Location of an undesirable facility in a polygonal region with forbidden zones

In this paper, we develop the problem of locating an undesirable facility in a bounded polygonal region (with forbidden polygonal zones), using Euclidean distances, under an objective function that generalizes the maximin and maxisum criteria, and includes other criteria such as the linear combinations of these criterions. We identify a finite dominating set (finite set of points to which an optimal solution must belong) for this problem and show that an optimum solution can be found in polynomial time in the number of vertices of the polygons in the model and the number of existing facilities.     

Finite problems and the logic of the weak law of excluded middle

A new characteristic of propositional formulas as operations on finite problems, the cardinality of a sufficient solution set, is defined. It is proved that if a formula is deducible in the logic of the weak law of excluded middle, then the cardinality of a sufficient solution set is bounded by a constant depending only on the number of variables; otherwise, the accessible cardinality of a sufficient solution set is close to (greater than the nth root of) its trivial upper bound. This statement is an analog of the authors result about the algorithmic complexity of sets obtained as values of propositional formulas, which was published previously. Also, we introduce the notion of Kolmogorov complexity of finite problems and obtain similar results.Translated from Matematicheskie Zametki, vol. 77, no. 2, 2005, pp. 291–302.Original Russian Text Copyright © 2005 by A. V. Chernov.This revised version was published online in April 2005 with a corrected issue number.     

New reformulation and feasible semismooth Newton method for a class of stochastic linear complementarity problems

A class of stochastic linear complementarity problems (SLCPs) with finitely many realizations is considered. We first formulate the problem as a new constrained minimization problem. Then, we propose a feasible semismooth Newton method which yields a stationary point of the constrained minimization problem. We study the condition for the level set of the objective function to be bounded. As a result, the condition for the solution set of the constrained minimization problem is obtained. The global and quadratic convergence of the proposed method is proved under certain assumptions. Preliminary numerical results show that this method yields a reasonable solution with high safety and within a small number of iterations.     

Borsuk''''s Problem in a Special Normed Space

Borsuk's problem is a famous problem in combinatorial geometry. It deals with the problem of partitioning a set into parts of smaller diameter. The problem was posed by the well-known Polish mathematician K. Borsuk in 1933. Many results have been obtained since then. In this paper, we discuss the Borsuk's problem in the     

On Borsuk’s Conjecture for Two-Distance Sets

In this paper, we answer Larman’s question on Borsuk’s conjecture for two-distance sets. We find a two-distance set consisting of 416 points on the unit sphere $S^{64}\subset\mathbb{R}^{65}$ which cannot be partitioned into 83 parts of smaller diameter. This also reduces the smallest dimension in which Borsuk’s conjecture is known to be false. Other examples of two-distance sets with large Borsuk numbers are given.     

On a series of problems related to the Borsuk and Nelson-Erdős-Hadwiger problems

In the present paper, a series of problems connecting the Borsuk and Nelson-Erd?s-Hadwiger classical problems in combinatorial geometry is considered. The problem has to do with finding the number χ(n, a, d) equal to the minimal number of colors needed to color an arbitrary set of diameter d in n-dimensional Euclidean space in such a way that the distance between points of the same color cannot be equal to a. Some new lower bounds for the quantity χ(n, a, d) are obtained.     

Approximation par éléments finis de problèmes elliptiques d'optimisation de forme

We consider a problem of elliptic optimal design. The control is the shape of the domain on which the Dirichlet problem for the Laplace equation is posed. In dimension n=2, S?veràk proved that there exists an optimal domain in the class of all open subsets of a given bounded open set, whose complements have a uniformly bounded number of connected components. The proof (J. Math. Pures Appl. 72 (1993) 537–551) is based on the compactness of this class of domains with respect to the complementary-Hausdorff topology and the continuous dependence of the solutions of the Dirichlet Laplacian in H¹ with respect to it. In this Note we consider a finite-element discrete version of this problem and prove that the discrete optimal domains converge in that topology towards the continuous one as the mesh-size tends to zero. The key point of the proof is that finite-element approximations of the solution of the Dirichlet Laplacian converge in H¹ whenever the polygonal domains converge in the sense of that topology. To cite this article: D. Chenais, E. Zuazua, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Fixed Point Methods for the Complementarity Problem

This paper is concerned with iterative procedures for the monotone complementarity problem. Our iterative methods consist of finding fixed points of appropriate continuous maps. In the case of the linear complementarity problem, it is shown that the problem is solvable if and only if the sequence of iterates is bounded in which case summability methods are used to find a solution of the problem. This procedure is then used to find a solution of the nonlinear complementarity problem satisfying certain regularity conditions for which the problem has a nonempty bounded solution set.     

Bounded VC-Dimension Implies a Fractional Helly Theorem

We prove that every set system of bounded VC-dimension has a fractional Helly property. More precisely, if the dual shatter function of a set system $\FF$ is bounded by $o(m^k)$, then $\FF$ has fractional Helly number $k$. This means that for every $\alpha>0$ there exists a $\beta>0$ such that if $F_1,F_2,\ldots,F_n\in\FF$ are sets with $\bigcap_{i\in I}F_i\neq\emptyset$ for at least $\alpha{n\choose k}$ sets $I\subseteq\{1,2,\ldots,n\}$ of size $k$, then there exists a point common to at least $\beta n$ of the $F_i$. This further implies a $(p,k)$-theorem: for every $\FF$ as above and every $p\geq k$ there exists $T$ such that if $\GG\subseteq\FF$ is a finite subfamily where among every $p$ sets, some $k$ intersect, then $\GG$ has a transversal of size $T$. The assumption about bounded dual shatter function applies, for example, to families of sets in $\Rd$ definable by a bounded number of polynomial inequalities of bounded degree; in this case we obtain fractional Helly number $d{+}1$.     

一个半正Sturm-Liouville边值问题的n个解的存在性

通过构造与非线性项有关的辅助函数并考察这个辅助函数在有界集上的性质，对于Sturm-Liouville边值问题建立了几个解的存在性，其中非线性项是下有界的．同时，给出了正解和非平凡解的一个判别方法．主要工具是锥压缩与锥拉伸型的Krasnosel’skii不动点定理．     

Generic properties of the complementarity problem

Givenf: R ₊ ⁿ R ⁿ , the complementarity problem is to find a solution tox 0,f(x) 0, and x, f(x) = 0. Under the condition thatf is continuously differentiable, we prove that for a generic set of such anf, the problem has a discrete solution set. Also, under a set of generic nondegeneracy conditions and a condition that implies existence, we prove that the problem has an odd number of solutions.This work was partially supported by N.S.F. Grants GP-8007 and 010185.     

Ensuring the boundedness of the core of games with restricted cooperation

The core of a cooperative game on a set of players N is one of the most popular concepts of solution. When cooperation is restricted (feasible coalitions form a subcollection \(\mathcal{F}\) of 2 ^N ), the core may become unbounded, which makes its usage questionable in practice. Our proposal is to make the core bounded by turning some of the inequalities defining the core into equalities (additional efficiency constraints). We address the following mathematical problem: can we find a minimal set of inequalities in the core such that, if turned into equalities, the core becomes bounded? The new core obtained is called the restricted core. We completely solve the question when \(\mathcal{F}\) is a distributive lattice, introducing also the notion of restricted Weber set. We show that the case of regular set systems amounts more or less to the case of distributive lattices. We also study the case of weakly union-closed systems and give some results for the general case.     

Properties of continuous mappings of unbounded metric spaces

Suppose a closed unbounded set F R_n is a union of a finite number p of closed unbounded sets F_i that are pairwise disjoint, and suppose f is a continuous mapping of F into the metric space r⁽²⁾. With each set F_i there is associated a point at infinity _i, at which it is assumed that f has a finite limit A_i R⁽²⁾, i=1, 2, ..., p. It is proved that: 1) f is bounded on F; 2) if f is a real functional, then the set contains a smallest and a largest value; 3) if the distance between F_i and F_j is greater than zero whenever i j, then f is uniformly continuous on F.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, No. 3, pp. 422–427, March, 1991.     

Levitin–Polyak well-posedness by perturbations of split minimization problems

In this paper, we extend well-posedness notions to the split minimization problem which entails finding a solution of one minimization problem such that its image under a given bounded linear transformation is a solution of another minimization problem. We prove that the split minimization problem in the setting of finite-dimensional spaces is Levitin–Polyak well-posed by perturbations provided that its solution set is nonempty and bounded. We also extend well-posedness notions to the split inclusion problem. We show that the well-posedness of the split convex minimization problem is equivalent to the well-posedness of the equivalent split inclusion problem.     

A quantitative program for Hadwiger’s covering conjecture

In 1957,Hadwiger made a conjecture that every n-dimensional convex body can be covered by 2n translates of its interior.Up to now,this conjecture is still open for all n 3.In 1933,Borsuk made a conjecture that every n-dimensional bounded set can be divided into n + 1 subsets of smaller diameters.Up to now,this conjecture is open for 4 n 297.In this article we encode the two conjectures into continuous functions defined on the spaces of convex bodies,propose a four-step program to attack them,and obtain some partial results.     

A Regularization Newton Method for Solving Nonlinear Complementarity Problems

In this paper we construct a regularization Newton method for solving the nonlinear complementarity problem (NCP(F )) and analyze its convergence properties under the assumption that F is a P ₀ -function. We prove that every accumulation point of the sequence of iterates is a solution of NCP(F ) and that the sequence of iterates is bounded if the solution set of NCP(F ) is nonempty and bounded. Moreover, if F is a monotone and Lipschitz continuous function, we prove that the sequence of iterates is bounded if and only if the solution set of NCP(F ) is nonempty by setting , where is a parameter. If NCP(F) has a locally unique solution and satisfies a nonsingularity condition, then the convergence rate is superlinear (quadratic) without strict complementarity conditions. At each step, we only solve a linear system of equations. Numerical results are provided and further applications to other problems are discussed. Accepted 25 March 1998     

Control of a family of nonlinear dynamic systems under measurements with bounded disturbances

We consider a control synthesis problem for nonlinear dynamic systems under parametric uncertainty and bounded measurement noises. Because of bounded disturbances in measurements of the state vector and the nonlinearity in the control object, the initially formulated control synthesis problem for a family of nonlinear systems as a generalized Zubov problem is transformed into a symbiosis of generalized Zubov–Bulgakov problems. The main result of the paper is the analytic solution of a minimax synthesis problem, which yields a constructive method for finding an invariant set.