On two problems of choosing some subset of vectors with integer coordinates that has maximum norm of the sum of elements in Euclidean space

Under study are the two problems of choosing a subset of m vectors with the maximum norm of the sum of the elements from a set of n vectors in Euclidean space ℝ ^k . The vectors are assumed to have integer coordinates. Using the dynamic programming technique, some new optimal algorithms are suggested for solving the problems; these algorithms have pseudopolynomial time when the dimension of the space is fixed. The new algorithms have certain advantages over the availables: the vector subset problem can be solved faster for m < (k/2) ^k , while, after taking into account an additional restriction on the order of the vectors, the time complexity is k ^k−1 times less independently on m.     

Finding intersection of rectangles by range search

Three related rectangle intersection problems in k-dimensional space are considered: (1) find the intersections of a rectangle with a given set of rectangles, (2) find the intersecting pairs of rectangles as they are inserted into or deleted from an existing set of rectangles, and (3) find the intersecting pairs of a given set of rectangles. By transforming these problems into range search problems, one need not divide the intersection problem into two subproblems, namely, the edge-intersecting problem and the containment problem, as done by many previous studies. Furthermore, this approach can also solve these subproblems separately, if required. For the first problem the running time is O((log n)^2k−1 + s), where s is the number of intersecting pairs of rectangles. For the second problem the time needed to generate and maintain n rectangles is O(n(log n)^2k) and the time for each query is O((log n)^2k−1 + s). For the third problem the total time is O(n log n + n(log n)^2(k−1) + s) for k ≥ 1.     

Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic

We investigate the definability in monadic ∑₁¹ and monadic Π₁¹ of the problems REG_k, of whether there is a regular subgraph of degree k in some given graph, and XREG_k, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REG_k^k and XREG_k^k, respectively, for k ≥ 2 (all our graphs are undirected). Our motivation partly stems from the fact (which we prove here) that REG_k^k and XREG_k^k are logspace equivalent to CONN and REACH, respectively, for k ≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first - order reductions, monadic ∑₁¹ games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑₁¹ and monadic Π₁¹, and we compare the definability of these problems (in monadic ∑₁¹ and monadic Π₁¹ with their computational complexity (which varies from solvable using logspace to NP - complete).     

The initial boundary-value problem with a free surface condition for the penalized equations of aqueous solutions of polymers

In this paper, we study some nonlocal problems for the Kelvin-Voight equations (1) and the penalized Kelvin-Voight equations (2): the first and second initial boundary-value problems and the first and second time periodic boundary problems. We prove that these problems have global smooth solutions of the classW _∞ ¹ (ℝ⁺;W ₂ ^2+k (Ω)),k=1,2,...;Ω⊂ℝ³. Bibliography: 25 titles. Dedicated to N. N. Uraltseva on her jubilee Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 221, 1995, pp. 185–207. Translated by N. A. Karazeeva.     

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.     

Error estimates for mixed finite element methods for nonlinear parabolic problems

We consider a class of mixed finite element methods for nonlinear parabolic problems over a plane domain. The finite element spaces taken are Raviart-Thomas spaces of index k, k ? 0. We obtain optimal order L²- and almost optimal order L^∞-error estimates for the finite element solution and order optimal L²-error estimates for its gradient. We also derive the error estimates for the time derivatives of the solution. Our results extend those previously obtained by Johnson and Thomée for the corresponding linear problems with k ? 1.     

An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs

The maximum weight k-independent set problem has applications in many practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design layout and routing problem. Based on DAG (Directed Acyclic Graph) approach, an O(kn ²) time sequential algorithm is designed in this paper to solve the maximum weight k-independent set problem on weighted trapezoid graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph.     

Greedily Finding a Dense Subgraph

Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)² − O(n ^− 1/3) ≤ R ≤ (1/2 + n/2k)² + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k − 1) − O(1/k) ≤ R ≤ 2(n/k − 1) + O(n/k²) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming.     

Solving boundary-value problems ofx k -analytic functions for a semicircle

Integral representations of x^k-analytic functions (k=const>0) in terms of boundary values of analytic functions are given. Using these integral representations, three boundary-value problems of x^k-analytic functions for a semicircle are solved by quadratures. Bibliography: 4 titles. Translated fromObchyslyuval’na ta Prykladna Matematyka, No. 76, 1992, pp. 3–12.     

Enumeration of the bent functions of least deviation from a quadratic bent function

We study a construction of the bent functions of least deviation from a quadratic bent function, describe all these bent functions of 2k variables, and show that the quantity of them is 2 ^k (2¹ + 1) ... (2 ^k + 1). We find some lower bound on the number of the bent functions of least deviation from a bent function of the Maiorana-McFarland class.     

Dense Packing of Patterns in a Permutation

We study the length L _k of the shortest permutation containing all patterns of length k. We establish the bounds e ⁻² k ² < L _k ≤ (2/3 + o(1))k ². We also prove that as k → ∞, there are permutations of length (1/4 + o(1))k ² containing almost all patterns of length k. Received January 2, 2007     

Full low-frequency asymptotic expansion for second-order elliptic equations in two dimensions

The present paper contains the low-frequency expansions of solutions of a large class of exterior boundary value problems involving second-order elliptic equations in two dimensions. The differential equations must coincide with the Helmholtz equation in a neighbourhood of infinity, however, they may depart radically from the Helmholtz equation in any bounded region provided they retain ellipticity. In some cases the asymptotic expansion has the form of a power series with respect to k² and k² (ln k + a)^?1, where k is the wave number and a is a constant. In other cases it has the form of a power series with respect to k², coefficients of which depend polynomially on In k. The procedure for determining the full low-frequency expansion of solutions of the exterior Dirichlet and Neumann problems for the Helmholtz equation is included as a special case of the results presented here.     

Transmutation via the momentum plane

Transmutation methods are developed for equations of the form x² φ“ + x²(k²” - q?(x)) φ = (v² - (1/4)) φ, with v as spectral variable, which correspond to problems in quantum scattering theory at fixed energy k² (here v ? l + (1/2) with l complex angular momentum). Spectral formulas for transmutation kernels are constructed and the machinery of transmutation theory developed by the author for spectral variable k is shown to have a version here. General Kontrorovi?-Lebedev theorems are also proved.     

Correction of finite element eigenvalues for problems with natural or periodic boundary conditions

Recent results of Andrew and Paine for a regular Sturm-Liouville problem with essential boundary conditions are extended to problems with natural or periodic boundary conditions. These results show that a simple asymptotic correction technique of Paine, de Hoog and Anderssen reduces the error in the estimate of thekth eigenvalue obtained by the finite element method, with linear hat functions and mesh lengthh, fromO(k ⁴ h ²) toO(kh ²). Numerical results show the correction to be useful even for low values ofk.     

Upper bounds on the sum of powers of the degrees of a simple planar graph

For a simple planar graph G and a positive integer k, we prove the upper bound 2(n ? 1)^k + 4^k(n ? 4) + 2·3^k ? 2((δ + 1)^k ? δ^k)(3n ? 6 ? m) on the sum of the kth powers of the degrees of G, where n, m, and δ are the order, the size, and the minimum degree of G, respectively. The bound is tight for all m with 0?3n ? 6 ? m≤?n/2? ? 2 and δ = 3. We also present upper bounds in terms of order, minimum degree, and maximum degree of G. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:112‐123, 2011     

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.     

Proximal-like contraction methods for monotone variational inequalities in a unified framework I: Effective quadruplet and primary methods

Approximate proximal point algorithms (abbreviated as APPAs) are classical approaches for convex optimization problems and monotone variational inequalities. To solve the subproblems of these algorithms, the projection method takes the iteration in form of u ^k+1=P _Ω [u ^k −α _k d ^k ]. Interestingly, many of them can be paired such that [(u)\tilde]^k = P_\varOmega[u^k - b_kF(v^k)] = P_\varOmega[[(u)\tilde]^k - (d₂^k - G d₁^k)]\tilde{u}^{k} = P_{\varOmega}[u^{k} - \beta_{k}F(v^{k})] = P_{\varOmega}[\tilde {u}^{k} - (d_{2}^{k} - G d_{1}^{k})], where inf {β _k }>0 and G is a symmetric positive definite matrix. In other words, this projection equation offers a pair of directions, i.e., d₁^kd_{1}^{k} and d₂^kd_{2}^{k} for each step. In this paper, for various APPAs we present a unified framework involving the above equations. Unified characterization is investigated for the contraction and convergence properties under the framework. This shows some essential views behind various outlooks. To study and pair various APPAs for different types of variational inequalities, we thus construct the above equations in different expressions according to the framework. Based on our constructed frameworks, it is interesting to see that, by choosing one of the directions (d₁^kd_{1}^{k} and d₂^kd_{2}^{k}) those studied proximal-like methods always utilize the unit step size namely α _k ≡1.     

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.     

Worst-case time bounds for coloring and satisfiability problems

We consider worst case time bounds for certain NP-complete problems. In particular, we consider the (k,2)-satisfiability problem which includes as special cases some canonical problems such as graph coloring and satisfiability. For the (k,2)-satisfiability problem, we present a randomized algorithm that runs in time O^*((k!)^n/k).² This bound is equivalent to O((k/c_k)ⁿ) with c_k increasing to the asymptotic limit e. For k11, we improve upon the O((0.4518k)ⁿ) randomized bound of Eppstein [Proceedings of the 12th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 329–337]. A special case of (k,2)-satisfiability is k-colorability; here we achieve the above time bound for a slightly larger c_k that has the same asymptotic behavior.