Methods of summation and best approximation

Let λ={λ _k ⁿ } be a triangular method of summation,f ε L_p (1 ≤ p ≤ ∞), $$U_n (f,x,\lambda ) = \frac{{a_0 }}{2} + \sum _{k = 1}^n \lambda _k^n (a_k \cos kx + b_k \sin kx).$$ Consideration is given to the problem of estimating the deviations ∥f ? U_n (f, λ) ∥ L_p in terms of a best approximation E_n (f) L_p in abstract form (for a sequence of projectors in a Banach space). Various generalizations of known inequalities are obtained.     

Analytic semigroups of pseudodifferential operators on vector-valued Sobolev spaces

In this paper we study continuity and invertibility of pseudodifferential operators with non-regular Banach space valued symbols. The corresponding pseudodifferential operators generate analytic semigroups on the Sobolev spaces W _p ^k (? ⁿ , E) with k ∈ ?₀, 1 ≤ p ≤ ∞. Here E is an arbitrary Banach space. We also apply the theory to solve non-autonomous parabolic pseudodifferential equations in Sobolev spaces.     

Forbidden (0,1)-Vectors in Hyperplanes of ℝ n : The Restricted Case

In this paper we continue our investigation on “Extremal problems under dimension constraint” introduced in [2]. Let E(n, k) be the set of (0,1)-vectors in ? ⁿ with k one's. Given 1 ≤ m, w ≤ n let X ? E(n, m) satisfy span (X) ∩ E(n, w) = ?. How big can |X| be? This is the main problem studied in this paper. We solve this problem for all parameters 1 ≤ m, w ≤ n and n > n ₀(m, w).     

An adaptive memory algorithm for the k-coloring problem

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms.     

A 3-approximation algorithm for the facility location problem with uniform capacities

We consider the facility location problem where each facility can serve at most U clients. We analyze a local search algorithm for this problem which uses only the operations of add, delete and swap and prove that any locally optimum solution is no more than 3 times the global optimum. This improves on a result of Chudak and Williamson who proved an approximation ratio of ${3+2\sqrt{2}}$ for the same algorithm. We also provide an example which shows that any local search algorithm which uses only these three operations cannot achieve an approximation guarantee better than 3.     

The maximal solution of a restricted subadditive inequality in numerical analysis

For a fixed non-negative integerp, letU _2p = {U _2p (n)},n ≥ 0, denote the sequence that is defined by the initial conditionsU _2p (0) =U _2p (1) =U _2p (2) = =U _2p (2p) = 1 and the restricted subadditive recursion $$U_{2p} (n + 2p + 1) = \mathop {\min }\limits_{0 \leqslant l \leqslant p} (U_{2p} (n + l) + U_{2p} (n + 2p - l)),n \geqslant 0$$ U _2p is of importance in the theory of sequential search for simple real zeros of real valued continuous 2p-th derivatives In this paper, several closed form expressions forU _2p (n), n > 2p, are determined, thereby providing insight into the structure ofU _2p Two of the properties thus illuminated are (a) the existence of exactlyp + 1 limit points (1 + 1/(p + 1 +i), 0 ≤i ≤p) of the associated sequence {U _2p (n + 1)/U _2p (n)},n ≥ 0, and (b) the relevance toU _2p of the classic number theoretic function ord     

The maximal solution of a restricted subadditive inequality in numerical analysis

For a fixed non-negative integerp, letU _2p = {U _2p (n)},n ≥ 0, denote the sequence that is defined by the initial conditions $$U_{2p} (0) = U_{2p} (1) = U_{2p} (2) = = U_{2p} (2p) = 1$$ and the restricted subadditive recursion $$U_{2p} (n + 2p + 1) = \mathop {\min }\limits_{0 \leqslant / \leqslant p} (U_{2p} (n + l) + U_{2p} (n + 2p - l)),n \geqslant 0$$ U _2p is of importance in the theory of sequential search for simple real zeros of real valued continuous 2p-th derivatives In this paper, several closed form expressions forU _2p (n), n > 2p, are determined, thereby providing insight into the structure ofU _2p Two of the properties thus illuminated are (a) the existence of exactlyp + 1 limit points (1 + 1/(p + 1 +i), 0 ≤i ≤p) of the associated sequence {U _2p (n + 1)/U _2p (n)},n ≥ 0, and (b) the relevance toU _2p of the classic number theoretic function ord     

On linear and semidefinite programming relaxations for hypergraph matching

The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are the following:

We consider the standard linear programming relaxation of the problem. We provide an algorithmic proof of a result of Füredi, Kahn and Seymour, showing that the integrality gap is exactly ${k-1+\frac{1}{k}}$ for k-uniform hypergraphs, and is exactly k ? 1 for k-partite hypergraphs. This yields an improved approximation algorithm for the weighted 3-dimensional matching problem. Our algorithm combines the use of the iterative rounding method and the fractional local ratio method, showing a new way to round linear programming solutions for packing problems.

We study the strengthening of the standard LP relaxation by local constraints. We show that, even after linear number of rounds of the Sherali-Adams lift-and-project procedure on the standard LP relaxation, there are k-uniform hypergraphs with integrality gap at least k ? 2. On the other hand, we prove that for every constant k, there is a strengthening of the standard LP relaxation by only a polynomial number of constraints, with integrality gap at most ${\frac{k+1}{2}}$ for k-uniform hypergraphs. The construction uses a result in extremal combinatorics.

We consider the standard semidefinite programming relaxation of the problem. We prove that the Lovász ${\vartheta}$ -function provides an SDP relaxation with integrality gap at most ${\frac{k+1}{2}}$ . The proof gives an indirect way (not by a rounding algorithm) to bound the ratio between any local optimal solution and any optimal SDP solution. This shows a new connection between local search and linear and semidefinite programming relaxations.

     

Approximation Algorithms for Maximization Problems Arising in Graph Partitioning

Given a graph G = (V, E), a weight function w: E → R⁺, and a parameter k, we consider the problem of finding a subset U  V of size k that maximizes: Max-Vertex Cover_k: the weight of edges incident with vertices in U,Max-Dense Subgraph_k: the weight of edges in the subgraph induced by U,Max-Cut_k: the weight of edges cut by the partition (U, V\U),Max-Uncut_k: the weight of edges not cut by the partition (U, V\U).For each of the above problems we present approximation algorithms based on semidefinite programming and obtain approximation ratios better than those previously published. In particular we show that if a graph has a vertex cover of size k, then one can select in polynomial time a set of k vertices that covers over 80% of the edges.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

Optimal selection of thek best of a sequence withk stops

We first consider the situation in which the decision-maker is allowed to have five choices with purpose to choose exactly the five absolute best candidates fromN applicants. The optimal stopping rule and the maximum probability of making the right five-choice are given for largeN εN, the maximum asymptotic value of the probability of the best choice being lim _N→∝ P (win) ≈ 0.104305. Then, we study the general problem of selecting thek best of a sequence withk stops, constructing first a rough solution for this problem. Using this suboptimal solution, we find an approximation for the optimal probability valuesP _k of the form $$P_k \approx \frac{1}{{(e - 1)k + 1}}$$ for any k εN.     

On packing and coloring hyperedges in a cycle

Given a hypergraph and k different colors, we study the problem of packing and coloring a subset of the hyperedges of the hypergraph as paths in a cycle such that the total profit of the hyperedges selected is maximized, where each physical link e_j on the cycle is used at most c_j times, each hyperedge h_i has its profit p_i and any two paths, each spanning all nodes of its corresponding hyperedge, must be assigned different colors if they share a common physical link. This new problem arises in optical communication networks, and it is called the Maximizing Profits when Packing and Coloring Hyperedges in a Cycle problem (MPPCHC).In this paper, we prove that the MPPCHC problem is NP-hard and then present an algorithm with approximation ratio 2 for this problem. For the special case where each hyperedge has the same profit 1 and each link e_j has same capacity k, we propose an algorithm with approximation ratio .     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

Bounds for consecutive kth power residues in the Eisenstein integers

This paper extends to the Eisenstein integers a + b? (a, bτZ, ?² + ? + 1 = 0) the problem of the existence of a bound on the size of a sequence of m consecutive kth powe residues of p, for all but a finite number of primes p and independent of p. The least such bound is denoted by Λ_E(k, m). It is shown that Λ_E(k, 2) is finite for k = 2, 3, 4 or 6n + 1. On the other hand, for every k, Λ_E(2k, 3) = Λ_E(3k, 4) = Λ_E(k, 6) = ∞. Similar results are obtained for the related bound for m consecutives all in the same coset modulo the subgroup of kth power residues.     

A RECOGNITION PROBLEM IN CONVERTING LINEAR PROGRAMMING TO NETWORK FLOW MODELS

The main goal of this paper is to study the following combinatorial problem.given a finite set E={e1,e2,…em} and a subset familly σ={S1,S2,…,Sn}of E,does there exist a tree T with the edge set E such that each induced subgraph T[Si] of Si is precisely a path (1≤i≤k)?     

Approximation Algorithms for Dispersion Problems

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the k-set packing problem is to find a maximum weight sub-collection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and a natural local search has been shown to approximate it to within a factor of roughly k − 1. However, neither paradigm can yield approximations that improve on this.We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. This is the first asymptotic improvement over the straightforward ratio of k.     

A modified greedy algorithm for dispersively weighted 3-set cover

The set cover problem is that of computing a minimum weight subfamily F^′, given a family F of weighted subsets of a base set U, such that every element of U is covered by some subset in F^′. The k-set cover problem is a variant in which every subset is of size at most k. It has been long known that the problem can be approximated within a factor of by the greedy heuristic, but no better bound has been shown except for the case of unweighted subsets. In this paper we consider approximation of a restricted version of the weighted 3-set cover problem, as a first step towards better approximation of general k-set cover problem, where any two distinct subset costs differ by a multiplicative factor of at least 2. It will be shown, via LP duality, that an improved approximation bound of H(3)-1/6 can be attained, when the greedy heuristic is suitably modified for this case. A key to our algorithm design and analysis is the Gallai-Edmonds structure theorem for maximum matchings.     

On subgroups of hypercentral type of finite groups

The main purpose of this paper is to analyze the influence on the structure of a finite group of some subgroups lying in the hypercenter. More precisely, we prove the following: Let \(\mathfrak{F}\) be a Baer-local formation. Given a group G and a normal subgroup E of G, let \(Z_\mathfrak{F} (G)\) contain a p-subgroup A of E which is maximal being abelian and of exponent dividing p ^k , where k is some natural number, k ≠ 1 if p = 2 and the Sylow 2-subgroups of E are non-abelian. Then E/O _p′ (E) ≤ \(Z_\mathfrak{F} \) (G/O _p′ (E)) (Theorem 1). Some well-known results turn out to be consequences of this theorem.     

Variable space search for graph coloring

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. We propose a new local search methodology, called Variable Space Search, which we apply to the k-coloring problem. The main idea is to consider several search spaces, with various neighborhoods and objective functions, and to move from one to another when the search is blocked at a local optimum in a given search space. The k-coloring problem is thus solved by combining different formulations of the problem which are not equivalent, in the sense that some constraints are possibly relaxed in one search space and always satisfied in another. We show that the proposed algorithm improves on every local search used independently (i.e., with a unique search space), and is competitive with the currently best coloring methods, which are complex hybrid evolutionary algorithms.     

Global convergence properties of two modified BFGS-type methods

This article studies a modified BFGS algorithm for solving smooth unconstrained strongly convex minimization problem. The modified BFGS method is based on the new quasi-Newton equation B_k+1s_k=yk where y_k*, =yk + A_ks_k andA _k is a matrix. Wei, Li and Qi [WLQ] have proven that the average performance of two of those algorithms is better than that of the classical one. In this paper, we prove the global convergence of these algorithms associated to a general line search rule.