Violator spaces: Structure and algorithms

Sharir and Welzl introduced an abstract framework for optimization problems, called LP-type problems or also generalized linear programming problems, which proved useful in algorithm design. We define a new, and as we believe, simpler and more natural framework: violator spaces, which constitute a proper generalization of LP-type problems. We show that Clarkson's randomized algorithms for low-dimensional linear programming work in the context of violator spaces. For example, in this way we obtain the fastest known algorithm for the P-matrix generalized linear complementarity problem with a constant number of blocks. We also give two new characterizations of LP-type problems: they are equivalent to acyclic violator spaces, as well as to concrete LP-type problems (informally, the constraints in a concrete LP-type problem are subsets of a linearly ordered ground set, and the value of a set of constraints is the minimum of its intersection).     

Fuzzy closure spaces

Fuzzy topological spaces do not constitute a natural boundary for the validity of theorems, but many results can be extended to what are called fuzzy closure spaces (or fcs's, for short). The notions of a subspace, a sum, and a product are extended to fcs's. The hereditary, additivity, and productivity behaviour of compactness in fcs's is investigated and some weak forms of compactness and fuzzy continuous functions in fcs's are introduced. The interaction between fuzzy proximity spaces and fcs's is investigated; A necessary background is included for completeness.     

Extensions of L-fuzzy closure spaces

In this paper, we study the extension theory to L-fuzzy closure spaces, where L is a strictly two-sided, commutative quantale lattice. We give new notions such as L-fuzzy stack, L-fuzzy c-grill and trace of a point. Also, we construct order relation and equivalence relation between two extensions. Also, We introduce the concept of a principal extension of L-fuzzy closure space and study some of its applications.     

Sequential closure in product spaces

Let X denote the product of m-many second countable Hausdorff spaces. Main theorems: (1) If S?X is invariant under compositions, m is weakly accessible (resp., nonmeasurable), and F?S is sequentially closed and a sequential G_σ-set which is invariant under projections for finite sets (resp., F?S is sequentially open and sequentially closed), then F is closed. (2) If S?X is invariant under projections and m is nonmeasurable, then every sequentially continuous {0, 1} valued function on S is continuous. (3) A sequentially continuous {0, 1}-valued function on an m-adic space of nonmeasurable weight is continuous. Now let X denote the product of arbitrarily many W-spaces and S?X be invariant under compositions. (4) Then in S, the closure of any Q-open subset coincides with its sequential closure.     

Exchange properties in closure spaces

Four exchange properties, including the usual one, are discussed. Assuming the finiteness condition or a weaker condition (called minimal condition), all four are equivalent. But examples show that in general no two of the four properties are equivalent. Furthermore it is shown that all four properties and the minimal condition follow from the Existence Theorem for a basis.     

Simple games on closure spaces

LetN be a finite set. By a closure space we mean the family of the closed sets of a closure operator on 2 ^N satisfying the additional condition . A simple game on a closure space is a functionv: such that andv (N)=1. We assume simple games are monotonic. The coalitions are the closed sets of and the players are the elementsi∈N. We will give results concerning the structure of the core and the Weber set for this type of games. We show that a simple game is supermodular if and only if the game is a unanimity game and theCore ( ,v) is a stable set if and only if the gamev is a unanimity game. This work was supported by the project USE 97-191 of the University of Seville.     

Extreme point axioms for closure spaces

A pair (X,τ) of a finite set X and a closure operator τ:2^X→2^X is called a closure space. The class of closure spaces includes matroids as well as antimatroids. Associated with a closure space (X,τ), the extreme point operator ex:2^X→2^X is defined as ex(A)={p|p∈A,p∉τ(A-{p})}. We give characterizations of extreme point operators of closure spaces, matroids and antimatroids, respectively.     

Cauchy structures in closure and proximity spaces

Research supported by Hungarian National Foundation for Scientific Research, grant no. 2114.     

The closure of planar diffeomorphisms in Sobolev spaces

We characterize the (sequentially) weak and strong closure of planar diffeomorphisms in the Sobolev topology and we show that they always coincide. We also provide some sufficient condition for a planar map to be approximable by diffeomorphisms in terms of the connectedness of its counter-images, in the spirit of Young's characterisation of monotone functions. We finally show that the closure of diffeomorphisms in the Sobolev topology is strictly contained in the class INV introduced by Müller and Spector.     

Rank functions of closure spaces of finite rank

We characterize those functions that are the rank functions of closure spaces of finite rank. In case such a function is defined on a finite set, we are able to improve this characterization.     

On closure compatibility of ideal topological spaces and idempotency of the local closure function

Periodica Mathematica Hungarica - The aim of this paper is to continue the work started in Pavlovi? (Filomat 30(14):3725–3731, 2016) . We investigate further the properties of the local...     

WeightedL p closure theorems for spaces of entire functions

For a fixed weight Δ(dx) onR ¹ and a linear space ℋ ⊆L ^p(Δ) of entire functions that is closed under difference quotientsh(·)→(z−·) ⁻¹[h(z)−h(·)], theL ^p(Δ) closure of ℋ is studied and characterized in terms of the normsL(z), (z∈C ¹ of the evaluation functionalsh→h(z),h∈ℋ. Partially supported by DA-ARO-31-124-71-6182 and NSF GP-43011.     

The uniform closure of non-dense rational spaces on the unit interval

Let P_n denote the set of all algebraic polynomials of degree at most n with real coefficients. Associated with a set of poles a₁,a₂,…,a_n R[-1,1] we define the rational function spaces Associated with a set of poles a₁,a₂,… R[-1,1], we define the rational function spacesIt is an interesting problem to characterize sets a₁,a₂,… R[-1,1] for which P(a₁,a₂,…) is not dense in C[-1,1], where C[-1,1] denotes the space of all continuous functions equipped with the uniform norm on [-1,1]. Akhieser showed that the density of P(a₁,a₂,…) is characterized by the divergence of the series .In this paper, we show that the so-called Clarkson–Erdős–Schwartz phenomenon occurs in the non-dense case. Namely, if P(a₁,a₂,…) is not dense in C[-1,1], then it is “very much not so”. More precisely, we prove the following result.Theorem Let a₁,a₂,… R[-1,1]. Suppose P(a₁,a₂,…) is not dense in C[-1,1], that is,Then every function in the uniform closure of P(a₁,a₂,…) in C[-1,1] can be extended analytically throughout the set C -1,1,a₁,a₂,… .