An approximation scheme for a problem of search for a vector subset

We consider the following clustering problem: Given a vector set, find a subset of cardinality k and minimum square deviation from its mean. The distance between the vectors is defined by the Euclideanmetric. We present an approximation scheme (PTAS) that allows us to solve this problem with an arbitrary relative error ? in time O(n ^2/?+1(9/?)^3/? d), where n is the number of vectors of the input set and d denotes the dimension of the space.     

On the asymptotic optimality of a solution of the euclidean problem of covering a graph by <Emphasis Type="Italic">m</Emphasis> nonadjacent cycles of maximum total weight

In the problem of covering an n-vertex graph by m cycles of maximum total weight, it is required to find a family of m vertex-nonadjacent cycles such that it covers all vertices of the graph and the total weight of edges in the cover is maximum. The paper presents an algorithm for approximately solving the problem of covering a graph in Euclidean d-space R^d by m nonadjacent cycles of maximum total weight. The algorithm has time complexity O(n³). An estimate of the accuracy of the algorithm depending on the parameters d, m, and n is substantiated; it is shown that if the dimension d of the space is fixed and the number of covering cycles is m = o(n), then the algorithm is asymptotically exact.     

An approximation algorithm for finding a <Emphasis Type="Italic">d</Emphasis>-regular spanning connected subgraph of maximum weight in a complete graph with random weights of edges

An approximation algorithm is suggested for the problem of finding a d-regular spanning connected subgraph of maximum weight in a complete undirected weighted n-vertex graph. Probabilistic analysis of the algorithm is carried out for the problem with random input data (some weights of edges) in the case of a uniform distribution of the weights of edges and in the case of a minorized type distribution. It is shown that the algorithm finds an asymptotically optimal solution with time complexity O(n ²) when d = o(n). For the minimization version of the problem, an additional restriction on the dispersion of weights of the graph edges is added to the condition of the asymptotical optimality of the modified algorithm.     

On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

On distinct distances among points in general position and other related problems

A set of points in the plane is said to be in general position if no three of them are collinear and no four of them are cocircular. If a point set determines only distinct vectors, it is called parallelogram free. We show that there exist n-element point sets in the plane in general position, and parallelogram free, that determine only O(n ²/√log n) distinct distances. This answers a question of Erd?s, Hickerson and Pach. We then revisit an old problem of Erd?s: given any n points in the plane (or in d dimensions), how many of them can one select so that the distances which are determined are all distinct? — and provide (make explicit) some new bounds in one and two dimensions. Other related distance problems are also discussed.     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.     

A note on scheduling jobs with equal processing times and inclusive processing set restrictions

We consider the problem of scheduling n jobs on m parallel machines with inclusive processing set restrictions. Each job has a given release date, and all jobs have equal processing times. The objective is to minimize the makespan of the schedule. Li and Li (2015) have developed an O(n²+mn log?n) time algorithm for this problem. In this note, we present a modified algorithm with an improved time complexity of O(min{m, log?n} ? n log?n).     

Degree sum of a pair of independent edges and <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connectivity

Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z ₃-connected if and only if G is one of K _2,n?2, K _3,n?3, K _2,n?2 ⁺ , K _3,n?3 ⁺ or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].     

Two-weighted estimates for generalized fractional maximal operators on non-homogeneous spaces

Let μ be a nonnegative Borel measure on R ^d satisfying that μ(Q) ? l(Q)ⁿ for every cube Q ? R ⁿ , where l(Q) is the side length of the cube Q and 0 < n ? d.We study the class of pairs of weights related to the boundedness of radial maximal operators of fractional type associated to a Young function B in the context of non-homogeneous spaces related to the measure μ. Our results include two-weighted norm and weak type inequalities and pointwise estimates. Particularly, we give an improvement of a two-weighted result for certain fractional maximal operator proved in W.Wang, C. Tan, Z. Lou (2012).     

On boundary value problems for systems of nonlinear generalized ordinary differential equations

A general theorem (principle of a priori boundedness) on solvability of the boundary value problem dx = dA(t) · f(t, x), h(x) = 0 is established, where f: [a, b]×R ⁿ → R ⁿ is a vector-function belonging to the Carathéodory class corresponding to the matrix-function A: [a, b] → R ^n×n with bounded total variation components, and h: BV_s([a, b],R ⁿ ) → R ⁿ is a continuous operator. Basing on the mentioned principle of a priori boundedness, effective criteria are obtained for the solvability of the system under the condition x(t₁(x)) = B(x) · x(t ₂(x))+c ₀, where t _i: BV_s([a, b],R ⁿ ) → [a, b] (i = 1, 2) and B: BV_s([a, b], R ⁿ ) → R ⁿ are continuous operators, and c ₀ ∈ R ⁿ .     

On the sum of the L1 influences of bounded functions

Let f: {-1, 1}ⁿ → [-1, 1] have degree d as a multilinear polynomial. It is well-known that the total influence of f is at most d. Aaronson and Ambainis asked whether the total L₁ influence of f can also be bounded as a function of d. Ba?kurs and Bavarian answered this question in the affirmative, providing a bound of O(d³) for general functions and O(d²) for homogeneous functions. We improve on their results by providing a bound of d² for general functions and O(d log d) for homogeneous functions. In addition, we prove a bound of d/(2p) + o(d) for monotone functions, and provide a matching example.     

On finite alperin <Emphasis Type="Italic">p</Emphasis>-groups with homocyclic commutator subgroup

We study metabelian Alperin groups, i.e., metabelian groups in which every 2-generated subgroup has a cyclic commutator subgroup. It is known that, if the minimum number d(G) of generators of a finite Alperin p-group G is n ≥ 3, then d(G′) ≤ C _n ² for p≠ 3 and d(G′) ≤ C _n ² + C _n ³ for p = 3. The first section of the paper deals with finite Alperin p-groups G with p≠ 3 and d(G) = n ≥ 3 that have a homocyclic commutator subgroup of rank C _n ² . In addition, a corollary is deduced for infinite Alperin p-groups. In the second section, we prove that, if G is a finite Alperin 3-group with homocyclic commutator subgroup G- of rank C _n ² + C _n ³ , then G″ is an elementary abelian group.     

Generic hypersurface singularities

The problem considered here can be viewed as the analogue in higher dimensions of the one variable polynomial interpolation of Lagrange and Newton. Let x₁,...,x_r be closed points in general position in projective spacePn, then the linear subspaceV ofH⁰ (?ⁿ,O(d)) (the space of homogeneous polynomials of degreed on ?ⁿ) formed by those polynomials which are singular at eachx_i, is given by r(n + 1) linear equations in the coefficients, expressing the fact that the polynomial vanishes with its first derivatives at x₁,...,x_r. As such, the “expected” value for the dimension ofV is max(0,h⁰(O(d))?r(n+1)). We prove thatV has the “expected” dimension for d≥5 (theorem A). This theorem was first proven in [A] using a very complicated induction with many initial cases. Here we give a greatly simplified proof using techniques developed by the authors while treating the corresponding problem in lower degrees.     

Some variations on Tverberg’s theorem

Define T(d, r) = (d + 1)(r - 1) + 1. A well known theorem of Tverberg states that if n ≥ T(d, r), then one can partition any set of n points in R^d into r pairwise disjoint subsets whose convex hulls have a common point. The numbers T(d, r) are known as Tverberg numbers. Reay added another parameter k (2 ≤ k ≤ r) and asked: what is the smallest number n, such that every set of n points in R^d admits an r-partition, in such a way that each k of the convex hulls of the r parts meet. Call this number T(d, r, k). Reay conjectured that T(d, r, k) = T(d, r) for all d, r and k. In this paper we prove Reay’s conjecture in the following cases: when k ≥ [d+3/2], and also when d < rk/r-k - 1. The conjecture also holds for the specific values d = 3, r = 4, k = 2 and d = 5, r = 3, k = 2.     

Constructing permutation arrays from groups

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1, q) and PGL(2, q) with Frobenius maps to obtain new, improved lower bounds for M(n, d). We give new randomized algorithms. We give better lower bounds for M(n, d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for \(M(n,n-2)\) for all \(n\equiv 2 \pmod 3\) such that \(n+1\) is a prime power.     

The program iteration method in a game problem of guidance

Let a sequence of d-dimensional vectors n _k = (n _k ¹ , n _k ² ,..., n _k ^d ) with positive integer coordinates satisfy the condition n _k ^j = α _j m _k +O(1), k ∈ ?, 1 ≤ j ≤ d, where α ₁ > 0,..., α _d > 0 and {m _k } _k=1 ^∞ is an increasing sequence of positive integers. Under some conditions on a function φ: [0,+∞) → [0,+∞), it is proved that, if the sequence of Fourier sums \({S_{{m_k}}}\) (g, x) converges almost everywhere for any function g ∈ φ(L)([0, 2π)), then, for any d ∈ ? and f ∈ φ(L)(ln⁺ L) ^d?1([0, 2π) ^d ), the sequence \({S_{{n_k}}}\) (f, x) of rectangular partial sums of the multiple trigonometric Fourier series of the function f and the corresponding sequences of partial sums of all conjugate series converge almost everywhere.     

Ergodic theorems with arithmetical weights

We prove that the divisor function d(n) counting the number of divisors of the integer n is a good weighting function for the pointwise ergodic theorem. For any measurable dynamical system (X, A, ν, τ) and any f ∈ L ^p (ν), p > 1, the limit

$$\mathop {\lim }\limits_{n \to \infty } \frac{1}{{\Sigma _{k = 1}^nd\left( k \right)}}\sum\limits_{k = 1}^n {d\left( k \right)f\left( {{\tau ^k}x} \right)} $$

exists ν-almost everywhere. The proof is based on Bourgain’s method, namely the circle method based on the shift model. Using more elementary ideas we also obtain similar results for other arithmetical functions, like the θ(n) function counting the number of squarefree divisors of n and the generalized Euler totient function J _s (n) = Σ _d|n d ^s μ(n/d), s > 0.

     

A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function

Consider the resource allocation problem:minimize ∑ⁿ_i=1 f_i(x_i) subject to ∑ⁿ_i=1 x_i = N and x_i's being nonnegative integers, where each f_i is a convex function. The well-known algorithm based on the incremental method requires O(N log n + n) time to solve this problem. We propose here a new algorithm based on the Lagrange multiplier method, requiring O[n²(log N)²] time. The latter is faster if N is much larger than n. Such a situation occurs, for example, when the optimal sample size problem related to monitoring the urban air pollution is treated.     

The characterization problem for designs with the parameters of AG<Subscript>d</Subscript>(<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)

We start a new characterization of the geometric 2-design AG _d (n,q) among all simple 2-designs with the same parameters by handling the cases d ∈ {1,2,3,n — 2}. For d ≠ 1, our characterization is in terms of line sizes, and for d = 1 in terms of the number of affine hyperplanes. We also show that the number of non-isomorphic resolvable designs with the parameters of AG₁(n,q) grows exponentially with linear growth of n.