A New Fully Polynomial Time Approximation Scheme for the Knapsack Problem

A fully polynomial time approximation scheme (FPTAS) is presented for the classical 0-1 knapsack problem. The new approach considerably improves the necessary space requirements. The two best previously known approaches need O(n + 1/³) and O(n · 1/) space, respectively. Our new approximation scheme requires only O(n + 1/²) space while also reducing the running time.     

Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem

A vector merging problem is introduced where two vectors of length n are merged such that the k-th entry of the new vector is the minimum over of the -th entry of the first vector plus the sum of the first k – + 1 entries of the second vector. For this problem a new algorithm with O(n log n) running time is presented thus improving upon the straightforward O(n ²) time bound.The vector merging problem can appear in different settings of dynamic programming. In particular, it is applied for a recent fully polynomial time approximation scheme (FPTAS) for the classical 0–1 knapsack problem by the same authors.     

New Approximation Algorithms for Map Labeling with Sliding Labels

In this paper we present approximation algorithm for the following NP-hard map labeling problem: Given a set S of n distinct sites in the plane, one needs to place at each site a uniform square of maximum possible size such that all the squares are along the same direction. This generalizes the classical problem of labeling points with axis-parallel squares and restricts the most general version where the squares can have different orientations. We obtain factor-4 and factor- approximation algorithms for this problem. These algorithms also work for two generalized versions of the problem. We also revisit the problem of labeling each point with maximum uniform axis-parallel square pairs and improve the previous approximation factor of 4 to 3.     

Approximation Algorithms for Bounded Facility Location Problems

The bounded k-median problem is to select in an undirected graph G = (V,E) a set S of k vertices such that the distance from any vertex v V to S is at most a given bound d and the average distance from vertices V\S to S is minimized. We present randomized algorithms for several versions of this problem and we prove some inapproximability results. We also study the bounded version of the uncapacitated facility location problem and present extensions of known deterministic algorithms for the unbounded version.     

The Knapsack Sharing Problem: An Exact Algorithm

In this paper, we propose an exact algorithm for the knapsack sharing problem. The proposed algorithm seems quite efficient in the sense that it solves quickly some large problem instances. The problem is decomposed into a series of single constraint knapsack problems; and by applying the dynamic programming and another strategy, we solve optimally the original problem. The performance of the exact algorithm is evaluated on a set of medium and large problem instances (a total of 240 problem instances). This algorithm is parallelizable and this is one of its important feature.     

Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices

An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T = (V, E, w) with leaf set {1,..., n} such that d_T(i, j) M[i, j] for all i, j and is minimum, where d_T(i, j) is the distance between i and j on T. Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology. In this paper, we examine its computational complexity and approximability. When the distances satisfy the triangle inequality, we show that the minimum ultrametric tree problem can be approximated in polynomial time with error ratio 1.5(1 + log n), where n is the number of species. We also develop an efficient branch-and-bound algorithm for constructing the minimum ultrametric tree for both metric and non-metric inputs. The experimental results show that it can find an optimal solution for 25 species within reasonable time, while, to the best of our knowledge, there is no report of algorithms solving the problem even for 12 species.     

Approximation Algorithms for Quadratic Programming

We consider the problem of approximating the global minimum of a general quadratic program (QP) with n variables subject to m ellipsoidal constraints. For m=1, we rigorously show that an -minimizer, where error (0, 1), can be obtained in polynomial time, meaning that the number of arithmetic operations is a polynomial in n, m, and log(1/). For m 2, we present a polynomial-time (1- )-approximation algorithm as well as a semidefinite programming relaxation for this problem. In addition, we present approximation algorithms for solving QP under the box constraints and the assignment polytope constraints.     

Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colorability

Hypergraph 2-colorability, also known as set splitting, is a widely studied problem in graph theory. In this paper we study the maximization version of the same. We recast the problem as a special type of satisfiability problem and give approximation algorithms for it. Our results are valid for hypergraph 2-colorability, set splitting and MAX-CUT (which is a special case of hypergraph 2-colorability) because the reductions are approximation preserving. Here we study the MAXNAESP problem, the optimal solution to which is a truth assignment of the literals that maximizes the number of clauses satisfied. As a main result of the paper, we show that any locally optimal solution (a solution is locally optimal if its value cannot be increased by complementing assignments to literals and pairs of literals) is guaranteed a performance ratio of . This is an improvement over the ratio of attributed to another local improvement heuristic for MAX-CUT (C. Papadimitriou, Computational Complexity, Addison Wesley, 1994). In fact we provide a bound of for this problem, where k 3 is the minimum number of literals in a clause. Such locally optimal algorithms appear to subsume typical greedy algorithms that have been suggested for problems in the general domain of satisfiability. It should be noted that the NAESP problem where each clause has exactly two literals, is equivalent to MAX-CUT. However, obtaining good approximation ratios using semi-definite programming techniques (M. Goemans and D.P. Williamson, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994a, pp. 422–431) appears difficult. Also, the randomized rounding algorithm as well as the simple randomized algorithm both (M. Goemans and D.P. Williamson, SIAM J. Disc. Math, vol. 7, pp. 656–666, 1994b) yield a bound of for the MAXNAESP problem. In contrast to this, the algorithm proposed in this paper obtains a bound of for this problem.     

A Note on the Max-Min 0-1 Knapsack Problem

In this paper we propose new lower and upper bounds for the max-min 0-1 knapsack problem, employing a mixture of two relaxations. In addition, in order to expose whether the bounds are practical or not, we implement a method incorporating the bounds to achieve an optimal solution of the problem.     

An Improved Randomized Approximation Algorithm for Max TSP

We present an O(n³)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically , where n is the number of vertices in the input (undirected) graph. This improves the previous best.Part of work done while visiting City University of Hong Kong.     

Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-free Languages

For a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem and the construction of a parse tree for a stochastic context-free language, O(n³) time algorithms were known. For both problems, this paper shows slightly improved O(n³(log log n)^1/2/(log n)^1/2) time exact algorithms, which are obtained by combining Valiant's algorithm for context-free recognition with fast funny matrix multiplication. Moreover, this paper shows an O(n^2.776 + (1/)^O(1)) time approximation algorithm for the former problem and an O(n^2.976 log n + (1/)^O(1)) time approximation algorithm for the latter problem, each of which has a guaranteed approximation ratio 1 – for any positive constant , where the absolute value of the logarithm of the probability is considered as an objective value in the latter problem. The former algorithm is obtained from a non-trivial modification of the well-known O(n³) time dynamic programming algorithm, and the latter algorithm is obtained by combining Valiant's algorithm with approximate funny matrix multiplication. Several related results are shown too.     

A Semidefinite Programming Approach to the Quadratic Knapsack Problem

In order to gain insight into the quality of semidefinite relaxations of constrained quadratic 0/1 programming problems we study the quadratic knapsack problem. We investigate several basic semidefinite relaxations of this problem and compare their strength in theory and in practice. Various possibilities to improve these basic relaxations by cutting planes are discussed. The cutting planes either arise from quadratic representations of linear inequalities or from linear inequalities in the quadratic model. In particular, a large family of combinatorial cuts is introduced for the linear formulation of the knapsack problem in quadratic space. Computational results on a small class of practical problems illustrate the quality of these relaxations and cutting planes.     

Improved Approximation Algorithms for Maximum Graph Partitioning Problems

We consider the design of approximation algorithms for a number of maximum graph partitioning problems, among others MAX-k-CUT, MAX-k-DENSE-SUBGRAPH, and MAX-k-DIRECTED-UNCUT. We present a new version of the semidefnite relaxation scheme along with a better analysis, extending work of Halperin and Zwick (2002). This leads to an improvement over known approximation factors for such problems. The key to the improvement is the following new technique: It was already observed by Han et al. (2002) that a parameter-driven choice of the random hyperplane can lead to better approximation factors than obtained by Goemans and Williamson (1995). But it remained difficult to find a “good” set of parameters. In this paper, we analyze random hyperplanes depending on several new parameters. We prove that a sub-optimal choice of these parameters can be obtained by the solution of a linear program which leads to the desired improvement of the approximation factors. In this fashion a more systematic analysis of the semidefinite relaxation scheme is obtained.     

Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling

We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al. (Proc. 31st ACM STOC, 1999, pp. 622–631; http://www.eng.tau.ac.il/amotz/). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al. (ibid., 1999), while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al. (ibid., 1999), our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded; a straightforward consequence of this result is an improvement of the ratio of an optimal solution of the integer programming formulation of the JISP2 problem (see Spieksma, Journal of Scheduling, vol. 2, pp. 215–227, 1999) to its linear programming relaxation.     

Approximation algorithms and hardness results for labeled connectivity problems

Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s – t path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.     

Polynomial Time Approximation Scheme for the Rectilinear Steiner Arborescence Problem

Given a set N of n terminals in the first quadrant of the Euclidean plane E², find a minimum length directed tree rooted at the origin o, connecting to all terminals in N, and consisting of only horizontal and vertical arcs oriented from left to right or from bottom to top. This problem is called rectilinear Steiner arborescence problem, which has been proved to be NP-complete recently (Shi and Su, 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2000, to appear). In this paper, we present a polynomial time approximation scheme for this problem.     

A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree

This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly, ), which is an improvement over the existing 1.5-approximation.     

An Approach for Optimal Allocation of Safety Resources: Using the Knapsack Problem to Take Aggregated Cost‐Efficient Preventive Measures

On the basis of the combination of the well‐known knapsack problem and a widely used risk management technique in organizations (that is, the risk matrix), an approach was developed to carry out a cost‐benefits analysis to efficiently take prevention investment decisions. Using the knapsack problem as a model and combining it with a well‐known technique to solve this problem, bundles of prevention measures are prioritized based on their costs and benefits within a predefined prevention budget. Those bundles showing the highest efficiencies, and within a given budget, are identified from a wide variety of possible alternatives. Hence, the approach allows for an optimal allocation of safety resources, does not require any highly specialized information, and can therefore easily be applied by any organization using the risk matrix as a risk ranking tool.     

A Polynomial Time Approximation Scheme for the Problem of Interconnecting Highways

The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect n given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework (Arora, 1998; also available from http:www.cs.princeton.edu/~arora). For every fixed c > 1 and given any n line segments in the plane, a randomized version of the scheme finds a -approximation to the optimal cost in O(n ^O(c)log(n) time.     

Performance Analysis and Improvement for Some Linear On-Line Bin-Packing Algorithms

The study on one-dimensional bin packing problem may bring about many important applications such as multiprocessor scheduling, resource allocating, real-world planning and packing. Harmonic algorithms (including H _K, RH, etc.) for bin packing have been famous for their linear-time and on-line properties for a long time. This paper profoundly analyzes the average-case performance of harmonic algorithms for pieces of i.i.d. sizes, provides the average-case performance ratio of H _K under (0,d] (d 1) uniform distribution and the average-case performance ratio of RH under (0,1] uniform distribution. We also finished the discussion of the worst-case performance ratio of RH. Moreover, we propose a new improved version of RH that obtains better worst- and average-case performance ratios.