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.”     

Finding Robust Solutions Using Local Search

This paper investigates how a local search metaheuristic for continuous optimisation can be adapted so that it finds broad peaks, corresponding to robust solutions. This is relevant in problems in which uncertain or noisy data is present. When using a genetic or evolutionary algorithm, it is standard practice to perturb solutions once before evaluating them, using noise from a given distribution. This approach however, is not valid when using population-less techniques like local search and other heuristics that use local search. For those algorithms to find robust solutions, each solution needs to be perturbed and evaluated several times, and these evaluations need to be combined into a measure of robustness. In this paper, we examine how many of these evaluations are needed to reliably find a robust solution. We also examine the effect of the parameters of the noise distribution. Using a simple tabu search procedure, the proposed approach is tested on several functions found in the literature. This revised version was published online in August 2006 with corrections to the Cover Date.     

局部域上的仿交换算子与Schatten类性质

设Tb^s是局部域K上带符号b的仿交换算子，本文证明了当Tb^st定义式中函数A（ξ，η）满足一定的条件时，Tb^st∈Sp的充要条件是b∈Bp^s t 1/p。     

Local chain‐configuration dependence of the mechanisms of the chemical reaction of poly(vinyl chloride). IX. Novel results on stereoselectivity of chlorination reaction

A poly(vinyl chloride) (PVC) sample was chlorinated in solution in the presence of 2,2′‐azobisisobutyronitrile and by the fluid‐bed method. The aim was to evaluate the scope of the stereoselectivity of the chlorination reaction. The quantitative microstructural analysis of the residual PVC with a degree of chlorination was followed by ¹³C NMR spectroscopy. From the evolution of the content of isotactic (mm), heterotactic (mr), and syndiotactic (rr) triads and of mmmm, mmmr, and rmmr isotactic pentads in the unchlorinated parts of the polymer, it was unambiguously inferred that the chlorination reaction proceeds by a stereoselective mechanism in that the mr heterotactic triads are the most reactive structures followed by the isotactic triad at mmmr and rmmr pentads. This conclusion was confirmed on the basis of the Fourier transform infrared results. The results provide valuable information regarding the effect of tacticity and related local conformations in the chemical reactions of PVC. © 2003 Wiley Periodicals, Inc. J Polym Sci Part A: Polym Chem 41: 508–519, 2003     

Four‐dimensional couplings among BF and matter theories from BRST cohomology

The local and manifestly covariant Lagrangian interactions in four spacetime dimensions that can be added to a “free” model that describes a generic matter theory and an abelian BF theory are constructed by means of deforming the solution to the master equation on behalf of specific cohomological techniques.     

Multiscale variety in complex systems

The Law of Requisite Variety is a mathematical theorem relating the number of control states of a system to the number of variations in control that is necessary for effective response. The Law of Requisite Variety does not consider the components of a system and how they must act together to respond effectively. Here we consider the additional requirement of scale of response and the effect of coordinated versus uncoordinated response as a key attribute of complex systems. The components of a system perform a task, with a number of such components needed to act in concert to perform subtasks. We apply the resulting generalization—a Multiscale Law of Requisite Variety—to understanding effective function of complex biological and social systems. This allows us to formalize an understanding of the limitations of hierarchical control structures and the inadequacy of central control and planning in the solution of many complex social problems and the functioning of complex social organizations, e.g., the military, healthcare, and education systems. © 2004 Wiley Periodicals, Inc. Complexity 9: 37–45, 2004     

Interpolation by a Game

We introduce a notion of a real game (a generalisation of the Karchmer-Wigderson game (cf. [3]) and of real communication complexity, and relate this complexity to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols (defined in [4, Definition 2.2]) of small real communication complexity solving the monotone communication complexity problem associated with the bipartite perfect matching problem. This work is motivated by a research in interpolation theorems for prepositional logic (by a problem posed in [5, Section 8], in particular). Our main objective is to extend the communication complexity approach of [4, 5] to a wider class of proof systems. In this direction we obtain an effective interpolation in a form of a protocol of small real communication complexity. Together with the above mentioned lower bound for tree-like protocols this yields as a corollary a lower bound on the number of steps for particular semantic derivations of Hall's theorem (these include tree-like cutting planes proofs for which an exponential lower bound was demonstrated in [2]).     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

The Equivalence of Several Basic Theorems for Subdifferentials

Several different basic tools are used for studying subdifferentials. They are a nonlocal fuzzy sum rule in (Borwein et al., 1996; Zhu, 1996), a multidirectional mean value theorem in (Clarke and Ledyaev, 1994; Clarke et al., 1998), local fuzzy sum rules in (Ioffe, 1984, 1990) and an extremal principle in (Kruger and Mordukhovich, 1980; Mordukhovich, 1976, 1980, 1994). We show that all these basic results are equivalent and discuss some interesting consequences of this equivalence.     

ContributionsSign-balanced covering matrices

A q × n array with entries from 0, 1,…,q − 1 is said to form a difference matrix if the vector difference (modulo q) of each pair of columns consists of a permutation of [0, 1,… q − 1]; this definition is inverted from the more standard one to be found, e.g., in Colbourn and de Launey (1996). The following idea generalizes this notion: Given an appropriate δ (-[−1, 1]^t, a λq × n array will be said to form a (t, q, λ, Δ) sign-balanced matrix if for each choice C₁, C₂,…, C_t of t columns and for each choice = (₁,…,_t) Δ of signs, the linear combination ∑_j=1^t _jC_j contains (mod q) each entry of [0, 1,…, q − 1] exactly λ times. We consider the following extremal problem in this paper: How large does the number k = k(n, t, q, λ, δ) of rows have to be so that for each choice of t columns and for each choice (₁, …, _t) of signs in δ, the linear combination ∑_j=1^t _jC_j contains each entry of [0, 1,…, q t- 1] at least λ times? We use probabilistic methods, in particular the Lovász local lemma and the Stein-Chen method of Poisson approximation to obtain general (logarithmic) upper bounds on the numbers k(n, t, q, λ, δ), and to provide Poisson approximations for the probability distribution of the number W of deficient sets of t columns, given a random array. It is proved, in addition, that arithmetic modulo q yields the smallest array - in a sense to be described.