In this paper we consider the following natural generalization of two fundamental problems: the Set-Cover problem and the Min-Knapsack problem. We are given an hypergraph, each vertex has a nonnegative weight and each...
详细信息
ISBN:
(纸本)0898714346
In this paper we consider the following natural generalization of two fundamental problems: the Set-Cover problem and the Min-Knapsack problem. We are given an hypergraph, each vertex has a nonnegative weight and each edge has a nonnegative length. For a given threshold (l) over cap, our objective is to find a subset of the vertices with minimum total cost, such that at least a length of (l) over cap of the edges are covered. This problem is called the partial set cover problem. We present an O(\V\(2) + \H\) time, Delta(E)-approximation algorithm for this problem, where Delta(E) greater than or equal to 2 is an upper bound on the edge cardinality of the hypergraph, and \H\ is the size of the hypergraph (i.e. the sum of all its edges cardinalities). We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function.
In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow...
详细信息
In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides irs practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n log n) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
We consider the following problem: Given a graph with edge lengths satisfying the triangle inequality, partition its node set into p subsets, minimizing the total length of edges whose two ends are in the same subset....
详细信息
We consider the following problem: Given a graph with edge lengths satisfying the triangle inequality, partition its node set into p subsets, minimizing the total length of edges whose two ends are in the same subset. For this problem we present an approximation algorithm which comes to at most twice the optimal value. For clustering into two equal-sized sets, the exact bound on the maximum possible error ratio of our algorithm is between 1.686 and 1.7. (C) 1998 Elsevier Science B.V. All rights reserved.
This paper deals with vector covering problems in d-dimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0, 1](d). The goal is to partition X into a maximum number...
详细信息
This paper deals with vector covering problems in d-dimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0, 1](d). The goal is to partition X into a maximum number of parts, subject to the constraint that in every part the sum of all vectors is at least one in every coordinate. This problem is known to be NP-complete, and we are mainly interested in its on-line and off-line approximability. For the on-line version, we construct approximation algorithms with worst case guarantee arbitrarily close to 1/(2d) in d greater than or equal to 2 dimensions. This result contradicts a statement of Csirik and Frenk in [5] where it is claimed that, for d greater than or equal to 2, no on-line algorithm can have a worst case ratio better than zero. Moreover, we prove that, for d greater than or equal to 2, no on-line algorithm can have a worst case ratio better than 2/(2d + 1). For the off-line version, we derive polynomial time approximation algorithms with worst case guarantee Theta(1/log d). For d = 2, we present a very fast and very simple off-line approximation algorithm that has worst case ratio 1/2. Moreover, we show that a method from the area of compact vector summation can be used to construct off-line approximation algorithms with worst case ratio 1/d for every d greater than or equal to 2.
There are a number of VLSI problems that have a common structure. We investigate such a structure that leads to a unified approach for three independent VLSI layout problems: partitioning, placement, and via minimizat...
详细信息
There are a number of VLSI problems that have a common structure. We investigate such a structure that leads to a unified approach for three independent VLSI layout problems: partitioning, placement, and via minimization. Along the line, we first propose a linear-time approximation algorithm on maxcut and two closely related problems. k-coloring and maximal k-color ordering problem. The k-coloring is a generalization of the maxcut and the maximal k-color ordering is a generalization of the k-coloring. For a graph G with e edges and n vertices, our maxcut approximation algorithm runs in O(e + n) sequential time yielding a node-balanced maxcut with size at least (w(E) + w(E)/n)/2, improving the time complexity of O(e log e) known before. Building on the proposed maxcut technique and employing a height-balanced binary decomposition, we devise an O((e + n)log k) time algorithm for the k-coloring problem which always finds a k-partition of vertices such that the number of bad (or "defected") edges does not exceed (w(E)/k)((n - 1)/n)(log k), thus improving both the time complexity O(enk) and the bound e/k known before. The other related problem is the maximal k-color ordering problem that has been an open problem [16]. We show the problem is NP-complete, then present an approximation algorithm building on our k-coloring structure. A performance bound on maximal k-color ordering cost, 2kw(E)/3 is attained in O(ek) time. The solution quality of this algorithm is also tested experimentally and found to be effective.
Given a multigraph G = (V, E), the Edge Coloring Problem (ECP) calls for the minimum number chi of colors needed to color the edges in E so that all edges incident with a common node are assigned different colors. The...
详细信息
Given a multigraph G = (V, E), the Edge Coloring Problem (ECP) calls for the minimum number chi of colors needed to color the edges in E so that all edges incident with a common node are assigned different colors. The best known polynomial time approximation algorithms for ECP belong to a same family, which is likely to contain, for each positive integer k, an algorithm which uses at most [((2k + 1)chi + (2k - 2))/2k] colors. For k less than or equal to 5 the existence of the corresponding algorithm was shown, whereas for larger values of k the question is open. We show that, for any k such that the corresponding algorithm exists, it is possible to improve the algorithm so as to use at most [((2k + 1)chi + (2k - 3))/2k] colors. It is easily shown that the (2k - 3)/2k term cannot be reduced further, unless P = NP. We also discuss how our result can be used to extend the set of cases in which well-known conjectures on ECP are valid. (C) 1998 Elsevier Science B.V. All rights reserved.
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached de...
详细信息
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the number of brushes that can be sold in that city. What is the best route to take to sell the quota while traveling the least distance possible? Notice that unlike the standard traveling salesman problem, not only do we need to figure out the order in which to visit the cities, but we must decide the more fundamental question: which cities do we want to visit? In this paper we give the first approximation algorithm having a polylogarithmic performance guarantee for this problem, as well as for the slightly more general "prize-collecting traveling salesman problem" (PCTSP) of Balas, and a variation we call the "bank robber problem" (also called the "orienteering problem" by Golden, Levi, and Vohra). We do this by providing an O(log(2) k) approximation to the somewhat cleaner k-MST problem which is defined as follows. Given an undirected graph on n nodes with nonnegative edge weights and an integer k n, find the tree of least weight that spans k vertices. (If desired, one may specify in the problem a "root vertex" that must be in the tree as well.) Our result improves on the previous best bound of O(root k) of Ravi et al.
We give a concrete example of a family of natural graph-theoretic problems which behave better and better with respect to approximability but none of which are Likely to admit a polynomial time approximation scheme. M...
详细信息
We give a concrete example of a family of natural graph-theoretic problems which behave better and better with respect to approximability but none of which are Likely to admit a polynomial time approximation scheme. More specifically, the family exhibits problems with arbitrarily small, yet positive (assuming P not equal NP), approximation thresholds. The family of problems we give is the independent set problem on k-iterated total graphs, For All k greater than or equal to 1. (C) 1998 Published by Elsevier Science B.V. All rights reserved.
暂无评论