On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension

The problems under study are connected with the choice of a vector subset from a given finite set of vectors in the Euclidean space ℝ ^k . The sum norm and averaged square of the sumnorm are considered as the target functions (to be maximized). The optimal combinatorial algorithms with time complexity O(k ² n ^2k ) are developed for these problems. Thus, the polynomial solvability of these problems is proved for k fixed.     

Integer knapsack problems with set-up weights

The Integer Knapsack Problem with Set-up Weights (IKPSW) is a generalization of the classical Integer Knapsack Problem (IKP), where each item type has a set-up weight that is added to the knapsack if any copies of the item type are in the knapsack solution. The k-item IKPSW (kIKPSW) is also considered, where a cardinality constraint imposes a value k on the total number of items in the knapsack solution. IKPSW and kIKPSW have applications in the area of aviation security. This paper provides dynamic programming algorithms for each problem that produce optimal solutions in pseudo-polynomial time. Moreover, four heuristics are presented that provide approximate solutions to IKPSW and kIKPSW. For each problem, a Greedy heuristic is presented that produces solutions within a factor of 1/2 of the optimal solution value, and a fully polynomial time approximation scheme (FPTAS) is presented that produces solutions within a factor of ε of the optimal solution value. The FPTAS for IKPSW has time and space requirements of O(nlog n+n/ε ²+1/ε ³) and O(1/ε ²), respectively, and the FPTAS for kIKPSW has time and space requirements of O(kn ²/ε ³) and O(k/ε ²), respectively.     

Parameterizing above Guaranteed Values: MaxSat and MaxCut

In this paper we investigate the parameterized complexity of the problems MaxSat and MaxCut using the framework developed by Downey and Fellows. LetGbe an arbitrary graph havingnvertices andmedges, and letfbe an arbitrary CNF formula withmclauses onnvariables. We improve Cai and Chen'sO(2^2ckcm) time algorithm for determining if at leastkclauses of ac-CNF formulafcan be satisfied; our algorithm runs inO(|f| + k²φ^k) time for arbitrary formulae and inO(cm + ckφ^k) time forc-CNF formulae, where φ is the golden ratio . We also give an algorithm for finding a cut of size at leastk; our algorithm runs inO(m + n + k4^k) time. We then argue that the standard parameterization of these problems is unsuitable, because nontrivial situations arise only for large parameter values (k ≥ m/2), in which range the fixed-parameter tractable algorithms are infeasible. A more meaningful question in the parameterized setting is to ask whether m/2 + kclauses can be satisfied, or m/2 + kedges can be placed in a cut. We show that these problems remain fixed-parameter tractable even under this parameterization. Furthermore, for up to logarithmic values of the parameter, our algorithms for these versions also run in polynomial time.     

Clifford-Hermite-monogenic operators

In this paper we consider operators acting on a subspace ℳ of the space L ₂ (ℝ^m; ℂ_m) of square integrable functions and, in particular, Clifford differential operators with polynomial coefficients. The subspace ℳ is defined as the orthogonal sum of spaces ℳ_s,k of specific Clifford basis functions of L ₂(ℝ^m; ℂm). Every Clifford endomorphism of ℳ can be decomposed into the so-called Clifford-Hermite-monogenic operators. These Clifford-Hermite-monogenic operators are characterized in terms of commutation relations and they transform a space ℳ_s,k into a similar space ℳ_s′,k′. Hence, once the Clifford-Hermite-monogenic decomposition of an operator is obtained, its action on the space ℳ is known. Furthermore, the monogenic decomposition of some important Clifford differential operators with polynomial coefficients is studied in detail.     

Dense Fast Random Projections and Lean Walsh Transforms

Random projection methods give distributions over k×d matrices such that if a matrix Ψ (chosen according to the distribution) is applied to a finite set of vectors x _i ∈ℝ ^d the resulting vectors Ψx _i ∈ℝ ^k approximately preserve the original metric with constant probability. First, we show that any matrix (composed with a random ±1 diagonal matrix) is a good random projector for a subset of vectors in ℝ ^d . Second, we describe a family of tensor product matrices which we term Lean Walsh. We show that using Lean Walsh matrices as random projections outperforms, in terms of running time, the best known current result (due to Matousek) under comparable assumptions.     

Bony attractors

A new possible geometry of an attractor of a dynamical system, a bony attractor, is described. A bony attractor is the union of two parts. The first part is the graph of a continuous function defined on a subset of ∑ ^k , the set of bi-infinite sequences of integers m in the range 0 ≤ m < k. The second part is the union of uncountably many intervals contained in the closure of the graph. An open set of skew products over the Bernoulli shift (σω) _i = ω _i+1 with fiber [0,1] is constructed such that each system in this set has a bony attractor.     

Representing a Functional Curve by Curves with Fewer Peaks

In this paper, we study the problems of (approximately) representing a functional curve in 2-D by a set of curves with fewer peaks. Representing a function (or its curve) by certain classes of structurally simpler functions (or their curves) is a basic mathematical problem. Problems of this kind also find applications in applied areas such as intensity-modulated radiation therapy (IMRT). Let f\bf f be an input piecewise linear functional curve of size n. We consider several variations of the problems. (1) Uphill–downhill pair representation (UDPR): Find two nonnegative piecewise linear curves, one nondecreasing (uphill) and one nonincreasing (downhill), such that their sum exactly or approximately represents f\bf f. (2) Unimodal representation (UR): Find a set of unimodal (single-peak) curves such that their sum exactly or approximately represents f\bf f. (3) Fewer-peak representation (FPR): Find a piecewise linear curve with at most k peaks that exactly or approximately represents f\bf f. Furthermore, for each problem, we consider two versions. For the UDPR problem, we study its feasibility version: Given ε>0, determine whether there is a feasible UDPR solution for f\bf f with an approximation error ε; its min-ε version: Compute the minimum approximation error ε ^∗ such that there is a feasible UDPR solution for f\bf f with error ε ^∗. For the UR problem, we study its min-k version: Given ε>0, find a feasible solution with the minimum number k ^∗ of unimodal curves for f\bf f with an error ε; its min-ε version: given k>0, compute the minimum error ε ^∗ such that there is a feasible solution with at most k unimodal curves for f\bf f with error ε ^∗. For the FPR problem, we study its min-k version: Given ε>0, find one feasible curve with the minimum number k ^∗ of peaks for f\bf f with an error ε; its min-ε version: given k≥0, compute the minimum error ε ^∗ such that there is a feasible curve with at most k peaks for f\bf f with error ε ^∗. Little work has been done previously on solving these functional curve representation problems. We solve all the problems (except the UR min-ε version) in optimal O(n) time, and the UR min-ε version in O(n+mlog m) time, where m<n is the number of peaks of f\bf f. Our algorithms are based on new geometric observations and interesting techniques.     

Some Ramsey-type theorems for countably determined sets

 Let X be an infinite internal set in an ω¹-saturated nonstandard universe. Then for any coloring of [X] ^k , such that the equivalence E of having the same color is countably determined and there is no infinite internal subset of [X] ^k with all its elements of different colors (i.e., E is condensating on X), there exists an infinite internal set Z⊆X such that all the sets in [Z] ^k have the same color. This Ramsey-type result is obtained as a consequence of a more general one, asserting the existence of infinite internal Q-homogeneous sets for certain Q ⊆ [[X] ^k ] ^m , with arbitrary standard k≥ 1, m≥ 2. In the course of the proof certain minimal condensating countably determined sets will be described. Received: 17 October 2000 / Published online: 12 July 2002     

On a Class of Vector-Valued Sequences Associated with Multiplier Sequences

In this article we introduce the vector valued sequence space m(E_k,φ,∧),associated with themultiplier sequence ∧=(λ_k) of non-zero complex numbers,and the terms of the sequence are chosen from theseminormed spaces E_k,seminormed by f_k for all k∈N.This generalizes the sequence space m(φ) introducedand studied by Sargent.We study some of its properties like solidity,completeness,and obtain some inclusionresults.We also characterize the multiplier problem and obtain the corresponding spaces dual to m(E_k,φ,∧).We prove some general results too.     

On the use of AGE algorithm with a high accuracy Numerov type variable mesh discretization for 1D non-linear parabolic equations

In this paper, the use of N-AGE and Newton-N-AGE iterative methods on a variable mesh for the solution of one dimensional parabolic initial boundary value problems is considered. Using three spatial grid points, a two level implicit formula based on Numerov type discretization is discussed. The local truncation error of the method is of O(k²h_l^-1 +kh_l +h_l³)O({k^2h_l^{-1} +kh_l +h_l^3}), where h _l  > 0 and k > 0 are the step lengths in space and time directions, respectively. We use a special technique to handle singular parabolic equations. The advantage of using these algorithms is highlighted computationally.     

Solution of a covering problem related to labelled tournaments

Suppose we have a tournament with edges labelled so that the edges incident with any vertex have at most k distinct labels (and no vertex has outdegree 0). Let m be the minimal size of a subset of labels such that for any vertex there exists an outgoing edge labelled by one of the labels in the subset. It was known that m ≤ (^k+1₂) for any tournament. We show that this bound is almost best possible, by a probabilistic construction of tournaments with m = O(k²/log k). We give explicit tournaments with m = k^2−o(1). If the number of vertices is bounded by N < 2^k₁ we have a better upper bound of m = O(k log N), which is again almost optimal. We also consider a relaxation of this problem in which instead of the size of a subset of labels we minimize the total weight of a fractional set with analogous properties. In that case the optimal bound is 2k − 1. © 1996 John Wiley & Sons, Inc.     

On a class of some special sets on thek-skeleton of a convex compact set

In this paper, generalizing the notion of a path we define ak-area to be the setD={g(t):t ∈J} on thek-skeleton of a convex compact setK in a Hilbert space, whereg is a continuous injection map from thek-dimensional convex compact setJ to thek-skeleton ofK. We also define anE ^k-area onK, whereE ^k is ak-dimensional subspace, to be ak-area with the propertyπ(g(t))=t,t ∈π(K), whereπ is the orthogonal projection onE ^k. This definition generalizes the notion of an increasing path on the 1-skeleton ofK. The existence of such sets is studied whenK is a subset of a Euclidean space or of a Hilbert space. Finally some conjectures are quoted for the number of such sets in some special cases.     

On a characterization of convexity-preserving maps, Davidon’s collinear scalings and Karmarkar’s projective transformations

In a recent paper, the authors have proved results characterizing convexity-preserving maps defined on a subset of a not-necessarily finite dimensional real vector space as projective maps. The purpose of this note is three-fold. First, we state a theorem characterizing continuous, injective, convexity-preserving maps from a relatively open, connected subset of an affine subspace of ℝ ^m into ℝ ⁿ as projective maps. This result follows from the more general results stated and proved in a coordinate-free manner in the above paper, and is intended to be more accessible to researchers interested in optimization algorithms. Second, based on that characterization theorem, we offer a characterization theorem for collinear scalings first introduced by Davidon in 1977 for deriving certain algorithms for nonlinear optimization, and a characterization theorem for projective transformations used by Karmarkar in 1984 in his linear programming algorithm. These latter two theorems indicate that Davidon’s collinear scalings and Karmarkar’s projective transformations are the only continuous, injective, convexity-preserving maps possessing certain features that Davidon and Karmarkar respectively desired in the derivation of their algorithms. The proofs of these latter two theorems utilize our characterization of continuous, injective, convexity-preserving maps in a way that has implications to the choice of scalings and transformations in the derivation of optimization algorithms in general. The third purpose of this note is to point this out. Received: January 2000 / Accepted: November 2000?Published online January 17, 2001     

On samples of independent random vectors in spaces of infinitely increasing dimension

We study the asymptotic behavior of a set of random vectors ξ_i, i = 1,..., m, whose coordinates are independent and identically distributed in a space of infinitely increasing dimension. We investigate the asymptotics of the distribution of the random vectors, the consistency of the sets M _m⁽ⁿ⁾ = ξ₁,..., ξ_m and X _n^λ = x ∈ X _n: ρ(x) ≤ λn, and the mutual location of pairs of vectors. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 12, pp. 1706–1711, December, 1998.     

Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes

The Fast Johnson–Lindenstrauss Transform (FJLT) was recently discovered by Ailon and Chazelle as a novel technique for performing fast dimension reduction with small distortion from ℓ ₂ ^d to ℓ ₂ ^k in time O(max {dlog d,k ³}). For k in [Ω(log d),O(d ^1/2)], this beats time O(dk) achieved by naive multiplication by random dense matrices, an approach followed by several authors as a variant of the seminal result by Johnson and Lindenstrauss (JL) from the mid 1980s. In this work we show how to significantly improve the running time to O(dlog k) for k=O(d ^1/2−δ ), for any arbitrary small fixed δ. This beats the better of FJLT and JL. Our analysis uses a powerful measure concentration bound due to Talagrand applied to Rademacher series in Banach spaces (sums of vectors in Banach spaces with random signs). The set of vectors used is a real embedding of dual BCH code vectors over GF(2). We also discuss the number of random bits used and reduction to ℓ ₁ space. The connection between geometry and discrete coding theory discussed here is interesting in its own right and may be useful in other algorithmic applications as well.     

New error bounds and their applications to convergence analysis of iterative algorithms

We present two new error bounds for optimization problems over a convex set whose objective function f is either semianalytic or γ-strictly convex, with γ≥1. We then apply these error bounds to analyze the rate of convergence of a wide class of iterative descent algorithms for the aforementioned optimization problem. Our analysis shows that the function sequence {f(x ^k )} converges at least at the sublinear rate of k ^-ε for some positive constant ε, where k is the iteration index. Moreover, the distances from the iterate sequence {x ^k } to the set of stationary points of the optimization problem converge to zero at least sublinearly. Received: October 5, 1999 / Accepted: January 1, 2000?Published online July 20, 2000     

On cyclic codes of length $${2^{2^r}-1}$$ with two zeros whose dual codes have three weights

In 1976, Helleseth conjectured that two binary m-sequences of length 2 ^m − 1 can not have a three-valued crosscorrelation function when m is a power of 2. We show that this conjecture is true when −1 is a correlation value. In other words, if C_1,k{{\mathcal{C}}_{1,k}} is the cyclic code of length 2 ^m − 1 with two zeros α, α ^k , where α is a primitive element of \mathbbF_2^m{{\mathbb{F}}_{2^m}} and gcd(k, 2 ^m − 1) = 1, then its dual C_1,k^{^}{{\mathcal{C}}_{1,k}^{\perp}} can not have three weights when m is a power of 2.     

Hybrid Conjugate Gradient Algorithm for Unconstrained Optimization

In this paper a new hybrid conjugate gradient algorithm is proposed and analyzed. The parameter β _k is computed as a convex combination of the Polak-Ribière-Polyak and the Dai-Yuan conjugate gradient algorithms, i.e. β _k ^N =(1−θ _k )β _k ^PRP +θ _k β _k ^DY . The parameter θ _k in the convex combination is computed in such a way that the conjugacy condition is satisfied, independently of the line search. The line search uses the standard Wolfe conditions. The algorithm generates descent directions and when the iterates jam the directions satisfy the sufficient descent condition. Numerical comparisons with conjugate gradient algorithms using a set of 750 unconstrained optimization problems, some of them from the CUTE library, show that this hybrid computational scheme outperforms the known hybrid conjugate gradient algorithms. N. Andrei is a member of the Academy of Romanian Scientists, Splaiul Independenţei nr. 54, Sector 5, Bucharest, Romania.     

Orthogonal decompositions of Sobolev spaces in Clifford analysis

The space L ₂(G;ℂ _m ) of Clifford-algebra-valued functions in bounded domains G of ℝ ^m is decomposed into the orthogonal sum of the subspace of poly-left-monogenic functions of arbitrary order k≥1 and its orthogonal complement and as well into the orthogonal sum of the subspace of polyharmonic functions of arbitrary order k≥1 and its orthogonal complement. The complementary subspaces are given explicitly. In the particular case m=2, complex functions are involved. Although this case has to be treated separately, the results are as before. The proofs are based on proper higher-order Cauchy–Pompeiu formulas and Green functions for powers of the Laplacian. Received: July 4, 2000; in final form: January 7, 2001?Published online: December 19, 2001     

Approximation in weighted Hardy spaces

This paper is concerned with several approximation problems in the weighted Hardy spacesH ^p(Ω) of analytic functions in the open unit disc D of the complex plane ℂ. We prove that ifX is a relatively closed subset of D, the class of uniform limits onX of functions inH ^p(Ω) coincides, moduloH ^p(Ω), with the space of uniformly continuous functions on a certain hull ofX which are holomorphic on its interior. We also solve the simultaneous approximation problems of describing Farrell and Mergelyan sets forH ^p(Ω), giving geometric characterizations for them. By replacing approximating polynomials by polynomial multipliers of outer functions, our results lead to characterizations of the same sets with respect to cyclic vectors in the classical Hardy spacesH ^p(D), 1 ⪯p < ∞. Dedicated to Professor Nácere Hayek on the occasion of his 75th birthday.