Approximation algorithms for constructing some required structures in digraphs

We consider a new problem of constructing some required structures in digraphs, where all arcs installed in such required structures are supposed to be cut from some pieces of a specific material of length L. Formally, we consider the model: a digraph D = (V, A; w), a structure S and a specific material of length L, where w: A → R⁺, we are asked to construct a subdigraph D′ from D, having the structure S, such that each arc in D′ is constructed by a part of a piece or/and some whole pieces of such a specific material, the objective is to minimize the number of pieces of such a specific material to construct all arcs in D′.     

A parallel algorithm for constructing minimum spanning trees

The construction of minimum spanning trees (MSTs) of weighted graphs is a problem that arises in many applications. In this paper we will study a new parallel algorithm that constructs an MST of an N-node graph in time proportional to N lg N, on an $\text{N}\text{(}\text{lg}\text{N)-}\text{processor}$ computing system. The primary theoretical contribution of this paper is the new algorithm, which is an improvement over Sollin's parallel MST algorithm in several ways. On a more practical level, this algorithm is appropriate for implementation in VLSI technology.     

Approximation algorithms for free-label maximization

Inspired by air-traffic control and other applications where moving objects have to be labeled, we consider the following (static) point-labeling problem: given a set P of n points in the plane and labels that are unit squares, place a label with each point in P in such a way that the number of free labels (labels not intersecting any other label) is maximized. We develop efficient constant-factor approximation algorithms for this problem, as well as PTASs, for various label-placement models.     

Approximation algorithms for projective clustering

We consider the following two instances of the projective clustering problem: Given a set S of n points in and an integer k>0, cover S by k slabs (respectively d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. Let w^* be the smallest value so that S can be covered by k slabs (respectively d-cylinders), each of width (respectively diameter) at most w^*. This paper contains three main results: (i) For d=2, we present a randomized algorithm that computes O(klogk) strips of width at most w^* that cover S. Its expected running time is O(nk²log⁴n) if k²logkn; for larger values of k, the expected running time is O(n^2/3k^8/3log^14/3n). (ii) For d=3, a cover of S by O(klogk) slabs of width at most w^* can be computed in expected time O(n^3/2k^9/4polylog(n)). (iii) We compute a cover of by O(dklogk) d-cylinders of diameter at most 8w^* in expected time O(dnk³log⁴n). We also present a few extensions of this result.     

Approximation numbers of bounded operators

The theory of ideals of linear operators is well developed and has a lot of applications in theory and practise. The purpose of this paper is to give a first idea of a similar theory for bounded (nonlinear) operators. In view of applications we will not give an abstract (perhaps general nonsense) theory, but an example of a class λ_p of bounded operators with a structure similar to an $\text{L}$-module($\text{L}$ represents the class of all linear operators between Banach spaces), and applications to projection methods for solving equations with λ_p-type operators.     

Approximations for constructing tree-form structures using specific material with fixed length

Substituting for the ordinary objective to minimize the sum of lengths of all edges in some graph structure of a weighted graph, we propose a new problem of constructing certain tree-form structure in same graph, where all edges needed in such a tree-form structure are supposed to be cut from some pieces of a specific material with fixed length. More precisely, we study a new problem defined as follows: a weighted graph \(G=(V,E; w)\), a tree-form structure \(\mathcal{S}\) and some pieces of specific material with length L, where a length function \(w:E\rightarrow Q^+\), satisfying \(w(u,v) \le L\) for each edge uv in G, we are asked how to construct a required tree-form structure \(\mathcal{S}\) as a subgraph \(G'\) of G such that each edge needed in \(G'\) is constructed by a part of a piece of such a specific material, the new objective is to minimize the number of necessary pieces of such a specific material to construct all edges in \(G'\). For this new objective defined, we obtain three results: (1) We present a \(\frac{3}{2}\)-approximation algorithm to construct a spanning tree of G; (2) We design a \(\frac{3}{2}\)-approximation algorithm to construct a single-source shortest paths tree of G; (3) We provide a 4-approximation algorithms to construct a metric Steiner tree of G.     

Universality for bounded degree spanning trees in randomly perturbed graphs

We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph G_α on n vertices with δ(G_α) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph G_α∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ.     

Approximation algorithms for graph approximation problems

Several versions of the graph approximation problem are under study. Approximation algorithms for these problems are proposed, and performance guarantees of the algorithms are obtained. In particular, it is shown that the problem of approximation by graphs with a bounded number of connected components belongs to the class APX.     

Approximation algorithms for indefinite quadratic programming

We consider-approximation schemes for indefinite quadratic programming. We argue that such an approximation can be found in polynomial time for fixed andt, wheret denotes the number of negative eigenvalues of the quadratic term. Our algorithm is polynomial in 1/ for fixedt, and exponential int for fixed. We next look at the special case of knapsack problems, showing that a more efficient (polynomial int) approximation algorithm exists.Part of this work was done while the author was visiting Sandia National Laboratories, Albuquerque, New Mexico, supported by the U.S. Department of Energy under contract DE-AC04-76DP00789. Part of this work was also supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.     

Approximation algorithms for dynamic resource allocation

We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, generates utility, and determines the subsequent state of the activity. We study the complexity of, and approximation algorithms for, maximizing average utility.     

Approximation algorithms for Hamming clustering problems

We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to find p binary strings of length n that minimize the maximum Hamming distance between a string in S and the closest of the p strings; this minimum value is termed the p-radius of S and is denoted by . The related Hamming diameter p-clustering problem (HDC) is to split S into p groups so that the maximum of the Hamming group diameters is minimized; this latter value is called the p-diameter of S.We provide an integer programming formulation of HRC which yields exact solutions in polynomial time whenever k is constant. We also observe that HDC admits straightforward polynomial-time solutions when k=O(logn) and p=O(1), or when p=2. Next, by reduction from the corresponding geometric p-clustering problems in the plane under the L₁ metric, we show that neither HRC nor HDC can be approximated within any constant factor smaller than two unless P=NP. We also prove that for any >0 it is NP-hard to split S into at most pk^1/7− clusters whose Hamming diameter does not exceed the p-diameter, and that solving HDC exactly is an NP-complete problem already for p=3. Furthermore, we note that by adapting Gonzalez' farthest-point clustering algorithm [T. Gonzalez, Theoret. Comput. Sci. 38 (1985) 293–306], HRC and HDC can be approximated within a factor of two in time O(pkn). Next, we describe a 2^O(p/)k^O(p/)n²-time (1+)-approximation algorithm for HRC. In particular, it runs in polynomial time when p=O(1) and =O(log(k+n)). Finally, we show how to find in

Full-size image

time a set L of O(plogk) strings of length n such that for each string in S there is at least one string in L within distance (1+), for any constant 0<<1.     

Polynomially bounded algorithms for locatingp-centers on a tree

We discuss several forms of thep-center location problems on an undirected tree network. Our approach is based on utilizing results for rigid circuit graphs to obtain polynomial algorithms for solving the model. Duality theory on perfect graphs is used to define and solve the dual location model.     

Approximation algorithms for TTP(2)

We consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. It consists of designing a schedule for a sports league of n teams such that the total traveling costs of the teams are minimized. The most important variant of the traveling tournament problem imposes restrictions on the number of consecutive home games or away games a team may have. We consider the case where at most two consecutive home games or away games are allowed. We show that the well-known independent lower bound for this case cannot be reached and present two approximation algorithms for the problem. The first algorithm has an approximation ratio of ${3/2+\frac{6}{n-4}}$ in the case that n/2 is odd, and of ${3/2+\frac{5}{n-1}}$ in the case that n/2 is even. Furthermore, we show that this algorithm is applicable to real world problems as it yields close to optimal tournaments for many standard benchmark instances. The second algorithm we propose is only suitable for the case that n/2 is even and n????12, and achieves an approximation ratio of 1?+?16/n in this case, which makes it the first ${1+\mathcal{O}(1/n)}$ -approximation for the problem.     

Approximation algorithms for the Euclidean bipartite TSP

We study approximation results for the Euclidean bipartite traveling salesman problem (TSP). We present the first worst-case examples, proving that the approximation guarantees of two known polynomial-time algorithms are tight. Moreover, we propose a new algorithm which displays a superior average case behavior indicated by computational experiments.     

最大割问题和最大平分割问题基于半定规划松弛的近似算法

考虑每条边具有非负权重的无向图, 最大割问题要求将顶点集划分为两个集合使得它们之间的边的权重之和最大. 当最大割问题半定规划松弛的最优解落到二维空间时, Goemans将近似比从0.87856...改进为0.88456. 依赖于半定规划松弛的目标值与总权和的比值的曲线, 此曲线的最低点为0.88456, 当半定规划松弛的目标值与总权和的比值在0.5到0.9044之间时, 利用Gegenbauer多项式舍入技巧, 改进了Zwick的近似比曲线. 进一步, 考虑最大割问题的重要变形------最大平分割问题, 在此问题中增加了划分的两部分的点数相等的要求. 同样考虑了最大平分割问题半定规划松弛的最优解落到二维空间的情形, 并利用前述的Gegenbauer多项式舍入技巧得到0.7091-近似算法.     

Approximation algorithms for a vehicle routing problem

In this paper we investigate a vehicle routing problem motivated by a real-world application in cooperation with the German Automobile Association (ADAC). The general task is to assign service requests to service units and to plan tours for the units such as to minimize the overall cost. The characteristics of this large-scale problem due to the data volume involve strict real-time requirements. We show that the problem of finding a feasible dispatch for service units starting at their current position and serving at most k requests is NP-complete for each fixed k ≥ 2. We also present a polynomial time (2k − 1)-approximation algorithm, where again k denotes the maximal number of requests served by a single service unit. For the boundary case when k equals the total number |E| of requests (and thus there are no limitations on the tour length), we provide a -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs.