Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

Generalized monotone bifunctions and equilibrium problems

Using quasimonotone and pseudomonotone bifunctions, we derive existence results for the following equilibrium problem: given a closed and convex subsetK of a real topological vector space, find such that for allyK. In addtion, we study the solution set and the uniquencess of a solution. The paper generalizes results obtained recently for variational inequalities.     

Blow-up sets for linear diffusion equations in one dimension

We consider the heat equation in the half-line with Dirichlet boundary data which blow up in finite time. Though the blow-up set may be any interval [0,a], depending on the Dirichlet data, we prove that the effective blow-up set, that is, the set of points where the solution behaves like u(0,t), consists always only of the origin. As an application of our results we consider a system of two heat equations with a nontrivial nonlinear flux coupling at the boundary. We show that by prescribing the non-linearities the two components may have different blow-up sets. However, the effective blow-up sets do not depend on the coupling and coincide with the origin for both components.     

Existence and Structure of Optimal Solutions of Infinite-Dimensional Control Problems

In this work we analyze the structure of optimal solutions for a class of infinite-dimensional control systems. We are concerned with the existence of an overtaking optimal trajectory over an infinite horizon. The existence result that we obtain extends the result of Carlson, Haurie, and Jabrane to a situation where the trajectories are not necessarily bounded. Also, we show that an optimal trajectory defined on an interval [0,τ] is contained in a small neighborhood of the optimal steady-state in the weak topology for all t ∈ [0,τ] \backslash E , where E \subset [0,τ] is a measurable set such that the Lebesgue measure of E does not exceed a constant which depends only on the neighborhood of the optimal steady-state and does not depend on τ . Accepted 26 July 2000. Online publication 13 November 2000.     

Ahlfors-régularité des quasi-minima de Mumford–Shah

Let be an open set. We consider on Ω the competitors (U,K) for the reduced Mumford–Shah functional, that is to say the Mumford–Shah functional in which the -norm of U term is removed, where K is a closed subset of Ω and U is a function on ΩK with gradient in  . The main result of this paper is the following: there exists a constant c for which, whenever (U,K) is a quasi-minimizer for the reduced Mumford–Shah functional and B(x,r) is a ball centered on K and contained in Ω with bounded radius, the -measure of is bounded above by cr^N−1 and bounded below by c⁻¹r^N−1.     

Expectation-Stock Dynamics in Multi-Agent Fisheries

In this paper we consider a game-theoretic dynamic model describing the exploitation of a renewable resource. Our model is based on a Cournot oligopoly game where n profit-maximizing players harvest fish and sell their catch on m markets. We assume that the players do not know the law governing the reproduction of the resource. Instead they use an adaptive updating scheme to forecast the future fish stock. We analyze the resulting dynamical system which describes how the fish population and the forecasts (expectations) of the players evolve over time. We provide results on the existence and local stability of steady states. We consider the set of initial conditions which give non-negative trajectories converging to an equilibrium and illustrate how this set can be characterized. We show how such sets may change as some structural parameters of our model are varied and how these changes can be explained. This paper extends existing results in the literature by showing that they also hold in our two-dimensional framework. Moreover, by using analytical and numerical methods, we provide some new results on global dynamics which show that such sets of initial conditions can have complicated topological structures, a situation which may be particularly troublesome for policymakers.     

On Translational Clouds for a Convex Body

For a d-dimensional convex body K let C(K) denote the minimum size of translational clouds for K. That is, C(K) is the minimum number of mutually non-overlapping translates of K which do not overlap K and block all the light rays emanating from any point of K. In this paper we prove the general upper bound . Furthermore, for an arbitrary centrally symmetric d-dimensional convex body S we show . Finally, for the d-dimensional ball B^d we obtain the bounds .     

Lattices in rank one Lie groups over local fields

We prove that if is theK-rational points of aK-rank one semisimple group over a non archimedean local fieldK, thenG has cocompact non-arithmetic lattices and if char(K)>0 also non-uniform ones. We also give a general structure theorem for lattices inG, from which we confirm Serre's conjecture that such arithmetic lattices do not satisfy the congruence subgroup property.Partially supported by a grant from the Bi-national Science Foundation U.S.-Israel.     

Translative covering by homothetic copies

We show that for any convex bodyKE ² there exists a triangleT such that , where T is a suitable homothetic copy ofT with ratio . As a corollary we show that if (K _i) are homothetic copies of a given convex bodyKE ² with areaV(K)=1, then the condition is sufficient for the existence of a translative covering ofK by (K _i).     

Stability-Like Properties of Differential Inclusions

The properties of invariance, stability, asymptotic stability and attainability of a given compact set with respect to a differential inclusion, have weak and strong versions: the weak version requires existence of a trajectory with the corresponding property, while the strong one requires this property for all trajectories. The following statement is proven in the paper (under slight restrictions) for each of the above-mentioned properties: if K has the weak property with respect to , then there is a (regulation) mapping G such that G(x) F(x) x and G has the strong property with respect to G(x). In addition, certain regularity of the set of solutions of the last inclusion is claimed.     

Monotone trajectories of differential inclusions and functional differential inclusions with memory

The paper gives a necessary and sufficient condition for the existence of monotone trajectories to differential inclusionsdx/dt ∈S[x(t)] defined on a locally compact subsetX ofR ^p, the monotonicity being related to a given preorder onX. This result is then extended to functional differential inclusions with memory which are the multivalued case to retarded functional differential equations. We give a similar necessary and sufficient condition for the existence of trajectories which reach a given closed set at timet=0 and stay in it with the monotonicity property fort≧0.     

A Construction for Multisecret Threshold Schemes

A multisecret threshold scheme is a system that protects a number of secrets (or keys) among a group of participants, as follows. Given a set of n participants, there is a secret s _K associated with each k–subset K of these participants. The scheme ensures that s _K can be reconstructed by any group of t participants in K ( ). A lower bound has been established on the amount of information that participants must hold in order to ensure that any set of up to w participants cannot obtain any information about a secret with which they are not associated. In this paper, for parameters t=2 and w=n-k+t-1, we give a construction for multisecret threshold schemes that satisfy this bound.     

Existence of equilibria of set-valued maps on bounded epi-Lipschitz domains in Hilbert spaces without invariance conditions

In this paper, we provide a new result of the existence of equilibria for set-valued maps on bounded closed subsets K of Hilbert spaces. We do not impose either convexity or compactness assumptions on K but we assume that K has epi-Lipschitz sections, i.e. its intersection with suitable finite dimensional spaces is locally the epigraph of Lipschitz functions. In finite dimensional spaces, the famous Brouwer theorem asserts the existence of a fixed point for a continuous function from a compact convex set K to itself. Our result could be viewed as a kind of generalization of this classical result in the context of Hilbert spaces and when the function (or the set-valued map) does not necessarily map K into itself (K is not invariant under the map). Our approach is based firstly on degree theory for compact and for condensing set-valued maps and secondly on flows generated by trajectories of differential inclusions.     

An efficient fixed-parameter algorithm for 3-Hitting Set

Given a collection C of subsets of size three of a finite set S and a positive integer k, the 3-Hitting Set problem is to determine a subset S′S with |S′|k, so that S′ contains at least one element from each subset in C. The problem is NP-complete, and is motivated, for example, by applications in computational biology. Improving previous work, we give an O(2.270^k+n) time algorithm for 3-Hitting Set, which is efficient for small values of k, a typical occurrence in some applications. For d-Hitting Set we present an O(c^k+n) time algorithm with c=d−1+O(d⁻¹).     

Approximation algorithms for Hamming clustering problems

We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to find p binary strings of length n that minimize the maximum Hamming distance between a string in S and the closest of the p strings; this minimum value is termed the p-radius of S and is denoted by . The related Hamming diameter p-clustering problem (HDC) is to split S into p groups so that the maximum of the Hamming group diameters is minimized; this latter value is called the p-diameter of S.We provide an integer programming formulation of HRC which yields exact solutions in polynomial time whenever k is constant. We also observe that HDC admits straightforward polynomial-time solutions when k=O(logn) and p=O(1), or when p=2. Next, by reduction from the corresponding geometric p-clustering problems in the plane under the L₁ metric, we show that neither HRC nor HDC can be approximated within any constant factor smaller than two unless P=NP. We also prove that for any >0 it is NP-hard to split S into at most pk^1/7− clusters whose Hamming diameter does not exceed the p-diameter, and that solving HDC exactly is an NP-complete problem already for p=3. Furthermore, we note that by adapting Gonzalez' farthest-point clustering algorithm [T. Gonzalez, Theoret. Comput. Sci. 38 (1985) 293–306], HRC and HDC can be approximated within a factor of two in time O(pkn). Next, we describe a 2^O(p/)k^O(p/)n²-time (1+)-approximation algorithm for HRC. In particular, it runs in polynomial time when p=O(1) and =O(log(k+n)). Finally, we show how to find in

Full-size image

time a set L of O(plogk) strings of length n such that for each string in S there is at least one string in L within distance (1+), for any constant 0<<1.     

Sufficient conditions for viability under imperfect measurement

Viability theory gives a necessary and sufficient condition for the existence of a (set-valued) state feedback control such that all trajectories of the closed-loop system starting from the graph of a given tube in the state space remain in the tube. Here we investigate the same problem in the case where only incomplete and inexact measurement of the state is available. In the time-invariant case, we give a sufficient condition for the existence of anoutput feedback regulation map. The condition is shown to be equivalent to Haddad's viability condition if the measurement is perfect.     

The Asymptotics of the Number of Eigenvalues of a Three-Particle Lattice Schrödinger Operator

The Hamiltonian of a system of three quantum-mechanical particles moving on the three-dimensional lattice and interacting via zero-range attractive potentials is considered. The location of the essential and discrete spectra of the three-particle discrete Schrödinger operator H(K), where K is the three-particle quasimomentum, is studied. The absence of eigenvalues below the bottom of the essential spectrum of H(K) for all sufficiently small values of the zero-range attractive potentials is established.The asymptotics is found for the number of eigenvalues N(0,z) lying below . Moreover, for all sufficiently small nonzero values of the three-particle quasimomentum K, the finiteness of the number of eigenvalues below the essential spectrum of H(K) is established and the asymptotics of the number N(K,0) of eigenvalues of H(K) below zero is given.     

Equivariant K-Homology and Restriction to Finite Cyclic Subgroups

For a discrete group G, we prove that a G-map between proper G–CW-complexes induces an isomorphism in G-equivariant K-homology if it induces an isomorphism in C-equivariant K-homology for every finite cyclic subgroup C of G. As an application, we show that the source of the Baum–Connes assembly map, namely K _* ^G (E(G, in)), is isomorphic to K _* ^G (E(G, )), where E(G, ) denotes the classifying space for the family of finite cyclic subgroups of G. Letting be the family of virtually cyclic subgroups of G, we also establish that and related results.     

Deformation of Plates of Small Condensers and Belinskii's Problem

We study the homeomorphic embeddings of a compact set K, a union of nondegenerate continua, into which preserve the conformal moduli of all condensers whose plates are continua in K. Using a result by V. N. Dubinin together with the estimates for the conformal moduli of infinitesimal condensers, we prove that Belinskii's conjecture (that such a mapping extends to a Mobius automorphism of the whole space ), corroborated by the author in 1990 for n=2 is also valid for n>2 if the compact set in question is regular at some collection of (n+2) points. This essentially strengthens the previous result of the author (1992) in which regularity was required at each point of the compact set.     

Flocks of Infinite Hyperbolic Quadrics

Let K be a field containing a nonsquare and a quadratic extension. Let denote the unique involutory automorphism of F fixing K pointwise. For every field K such that the nonzero squares of K do not form an index 1 or 2 subgroup of , a construction is given which produces large numbers of infinite nearfield and non nearfield flocks of an infinite hyperbolic quadric in PG(3,K).