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⁻¹).     

Characterizing compact unions of two starshaped sets inR d

SetS inR ^d has propertyK ₂ if and only ifS is a finite union ofd-polytopes and for every finite setF in bdryS there exist points c₁,c₂ (depending onF) such that each point ofF is clearly visible viaS from at least one c_i,i = 1,2. The following characterization theorem is established: Let , d2. SetS is a compact union of two starshaped sets if and only if there is a sequence {S _j } converging toS (relative to the Hausdorff metric) such that each setS _j satisfies propertyK ₂. For , the sufficiency of the condition above still holds, although the necessity fails.     

On a generalization of the Gallai-Sylvester theorem

It is shown that ifS ^d , affS=aff ^d , and every hyperplane spanned by (a subset of)S misses fewer thank points ofS(k2), then (a) #Skm ifd=2m–1 is odd and (b) #Skm+1 ifd=2m is even. We also fully describe the extreme sets for which equality holds in (a) or in (b). For oddd the proofs are later modified to purely algebraic ones, and carry over to , where is an arbitrary field. For evend, (b) is generally not true when , but we prove some weaker inequalities that do hold over arbitrary fields.This is part of a Ph.D. thesis, supervised by Professor Micha A. Perles at the Hebrew University of Jerusalem. This research was supported in part by the Landau Center for Mathematical Research.     

Visible shorelines inR d

Summary LetC be a closed set inR ^d and letj be a fixed integer,j 1. The setS R ^d ~C is said to have aj-partition relative toC if there existj or fewer pointsc ₁,, c _j ofC such that each point ofS sees via the complement ofC at least one pointc _i. For every triple of integersd, p, j withd 0, p d + 1, j 1, there exists a smallest integerf(d, p, j) such that the following is true: IfC is a convexd-polytope inR ^d havingp vertices and ifS R ^d ~C, S has aj-partition relative toC if and only if everyf(d, p, j)-member subset of S has such a partition.ForC a convex polytope inR ² andS R ² ~C, all points ofS see via the complement ofC a common neighborhood in the boundary ofC if and only if every three points ofS see via the complement ofC such a neighborhood.A weak analogue of this result holds for arbitrary compact convex sets inR ^d .     

An improvement of the Ivanov bound

Let be a distance-regular graph of diameterd, valencyk andr=max{i|(c _i ,b _i )=(c ₁,b ₁)}. In this paper, we prove that

On the Positive Definiteness of Certain Functions

For a coinmutative senugoup (S, +, *) with involution and a function f : S → [0, ∞), the set S(f) of those p ≥ 0 such that f^P is a positive definite function on S is a closed subsemigroup of [0, ∞) containing 0. For S = (IR, +, x* = -x) it may happen that S(f) = { kd : k ∈ N₀ } for some d > 0, and it may happen that S(f) = {0} ? [d, ∞) for some d > O. If α > 2 and if S = (?, +, n* = -n) and f(n) = e^?[n]α or S = (IN₀, +, n* = n) and f(n) = e^nα, then S(f) ∪ (0, c) = ? and [d, ∞) ? S(f) for some d ≥; c > 0. Although (with c maximal and d minimal) we have not been able to show c = d in all cases, this equality does hold if S = ? and α ≥ 3.4. In the last section we give sinipler proofs of previously known results concerning the positive definiteness of x → e^?||x||α on normed spaces.     

An inequality relating the order,maximum degree,diameter and connectivity of a strongly connected digraph

We prove that if there is a strongly connected digraph of ordern, maximum degreed, diameterk and connectivityc, thennc d ^k–d /d–1+d+1. It improves the previous known results, and it, in fact, is the best possible for several interesting cases. A similar result for arc connectivity is also established.This project is supported by the National Natural Science Foundation of China.     

Spin depolarization decay rates in α-symmetric stable fields on cubic lattices

We study the asymptotic, long-time behavior of the energy function where {X_s : 0 ≤ s < ∞} is the standard random walk on the d-dimensional lattice Z^d, 1 < α ≤ 2, and f:R⁺ → R⁺ is any nondecreasing concave function. In the special case f(x) = x, our setting represents a lattice model for the study of transverse magnetization of spins diffusing in a homogeneous, α-stable, i.i.d., random, longitudinal field {λV(x) : x ∈ Z^d} with common marginal distribution, the standard α-symmetric stable distribution; the parameter λ describes the intensity of the field. Using large-deviation techniques, we show that S_c(λ α f) = lim_t→∞ E(t; λ f) exists. Moreover, we obtain a variational formula for this decay rate S_c. Finally, we analyze the behavior S_c(λ α f) as λ → 0 when f(x) = x^β for all 1 ≥ β > 0. Consequently, several physical conjectures with respect to lattice models of transverse magnetization are resolved by setting β = 1 in our results. We show that S_c(λ, α, 1) ≈ λ^α for d ≥ 3, λ^agr;(ln 1/λ)^α−1 in d = 2, and in d = 1. © 1996 John Wiley & Sons, Inc.     

On the Number of Vertices with Specified Eccentricity

The eccentricity of a vertex v in a graph is the maximum of the distances from v to all other vertices. The diameter of a graph is the maximum of the eccentricities of its vertices. Fix the parameters n, d, c. Over all graphs with order n and diameter d, we determine the maximum (within 1) and the minimum of the number of vertices with eccentricity c. Revised: May 7, 1999     

Fibrés d'intersection

Let f:XSbe a projective morphism of Noetherian schemes. We assume fpurely of relative dimension dand finite Tor-dimensional. We associate to d+1 invertible sheaves on Xa line bundle I _X/S ( ) on Sdepending additively on the , commuting to good base changes and which represents the integral along the fibres of fof the product of the first Chern classes of the . If d=0, I _X/S ( ) is the norm N _X/S ( ).     

Stabbing Simplices by Points and Flats

The following result was proved by Bárány in 1982: For every d≥1, there exists c _d >0 such that for every n-point set S in ℝ ^d , there is a point p∈ℝ ^d contained in at least c _d n ^d+1−O(n ^d ) of the d-dimensional simplices spanned by S. We investigate the largest possible value of c _d . It was known that c _d ≤1/(2 ^d (d+1)!) (this estimate actually holds for every point set S). We construct sets showing that c _d ≤(d+1)^−(d+1), and we conjecture that this estimate is tight. The best known lower bound, due to Wagner, is c _d ≥γ _d :=(d ²+1)/((d+1)!(d+1) ^d+1); in his method, p can be chosen as any centerpoint of S. We construct n-point sets with a centerpoint that is contained in no more than γ _d n ^d+1+O(n ^d ) simplices spanned by S, thus showing that the approach using an arbitrary centerpoint cannot be further improved.     

On the stretch factor of Delaunay triangulations of points in convex position

Let S be a finite set of points in the Euclidean plane. Let G be a geometric graph in the plane whose point set is S. The stretch factor of G is the maximum ratio, among all points p and q in S, of the length of the shortest path from p to q in G over the Euclidean distance |pq|. Keil and Gutwin in 1989 [11] proved that the stretch factor of the Delaunay triangulation of a set of points S in the plane is at most 2π/(3cos(π/6))≈2.42. Improving on this upper bound remains an intriguing open problem in computational geometry.In this paper we consider the special case when the points in S are in convex position. We prove that in this case the stretch factor of the Delaunay triangulation of S is at most ρ=2.33.     

Hilbert Functions, Residual Intersections, and Residually S2 Ideals

Let R be a homogeneous ring over an infinite field, IR a homogeneous ideal, and I an ideal generated by s forms of degrees d ₁,...,d _s so that codim( :I)s. We give broad conditions for when the Hilbert function of R/ or of R/( :I) is determined by I and the degrees d ₁,...,d _s . These conditions are expressed in terms of residual intersections of I, culminating in the notion of residually S ₂ ideals. We prove that the residually S ₂ property is implied by the vanishing of certain Ext modules and deduce that generic projections tend to produce ideals with this property.     

On Positive Sasakian Geometry

A Sasakian structure =(\xi,\eta,\Phi,g) on a manifold Mis called positiveif its basic first Chern class c₁( ) can be represented by a positive (1,1)-form with respect to its transverse holomorphic CR-structure. We prove a theorem that says that every positive Sasakian structure can be deformed to a Sasakian structure whose metric has positive Ricci curvature. This provides us with a new technique for proving the existence of positive Ricci curvature metrics on certain odd dimensional manifolds. As an example we give a completely independent proof of a result of Sha and Yang that for every nonnegative integer kthe 5-manifolds k#(S ²×S ³) admits metrics of positive Ricci curvature.     

Singular perturbed Markov chains and exact behaviors of simulated annealing processes

We study asymptotic properties of discrete and continuous time generalized simulated annealing processesX(·) by considering a class of singular perturbed Markov chains which are closely related to the large deviation of perturbed diffusion processes. Convergence ofX(t) in probability to a setS ₀ of desired states, e.g., the set of global minima, and in distribution to a probability concentrated onS ₀ are studied. The corresponding two critical constants denoted byd and withd are given explicitly. When the cooling schedule is of the formc/logt, X(t) converges weakly forc>0. Whether the weak limit depends onX(0) or concentrates onS ₀ is determined by the relation betweenc, d, and . Whenc>, the expression for the rate of convergence for each state is also derived.     

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.     

Approximation algorithms for projective clustering

We consider the following two instances of the projective clustering problem: Given a set S of n points in and an integer k>0, cover S by k slabs (respectively d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. Let w^* be the smallest value so that S can be covered by k slabs (respectively d-cylinders), each of width (respectively diameter) at most w^*. This paper contains three main results: (i) For d=2, we present a randomized algorithm that computes O(klogk) strips of width at most w^* that cover S. Its expected running time is O(nk²log⁴n) if k²logkn; for larger values of k, the expected running time is O(n^2/3k^8/3log^14/3n). (ii) For d=3, a cover of S by O(klogk) slabs of width at most w^* can be computed in expected time O(n^3/2k^9/4polylog(n)). (iii) We compute a cover of by O(dklogk) d-cylinders of diameter at most 8w^* in expected time O(dnk³log⁴n). We also present a few extensions of this result.     

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 .     

On the Summing Property of the Sobolev Embedding Operators

We prove that the Sobolev embedding operator S _d,k,p : , where 1/s=1/p-k/d , is (v,1) -absolutely summing for appropriate v > 1 . The result is optimal for s 2 .     

The Metric of Large Deviation Convergence

We construct a metric space of set functions ( , d) such that a sequence {P _n} of Borel probability measures on a metric space ( , d*) satisfies the full Large Deviation Principle (LDP) with speed {a _n} and good rate function I if and only if the sequence converges in ( , d) to the set function e ^–I . Weak convergence of probability measures is another special case of convergence in ( , d). Properties related to the LDP and to weak convergence are then characterized in terms of ( , d).