We introduce the following optimization version of the classical pattern matching problem (referred to as the maximum pattern matching problem). Given a two-dimensional rectangular text and a two-dimensional rectangul...
详细信息
We introduce the following optimization version of the classical pattern matching problem (referred to as the maximum pattern matching problem). Given a two-dimensional rectangular text and a two-dimensional rectangular pattern, find the maximum number of non-overlapping occurrences of the pattern in the text. Unlike the classical two-dimensional pattern matching problem, the maximum two-dimensional pattern matching problem is NP-complete. We devise polynomial time approximation algorithms and approximation schemes for this problem. We also briefly discuss how the approximation algorithms can be extended to include a number of other variants of the problem. (C) 2001 Elsevier Science B.V. All rights reserved.
We examine the bandwidth problem in circular-arc graphs, chordal graphs with a bounded number of leaves in the clique tree, and k-polygon graphs (fixed k). We show that all of these graph classes admit efficient appro...
详细信息
We examine the bandwidth problem in circular-arc graphs, chordal graphs with a bounded number of leaves in the clique tree, and k-polygon graphs (fixed k). We show that all of these graph classes admit efficient approximation algorithms which are based on exact or approximate bandwidth layouts of related interval graphs. Specifically, we obtain a bandwidth approximation algorithm for circular-arc graphs that executes in O(n log(2) n) time and has performance ratio 2, which is the best possible performance ratio of any polynomial time bandwidth approximation algorithm for circular-arc graphs. For chordal graphs with at most k leaves in the clique tree, we obtain a performance ratio of 2k in O(k(n+m)) time, and our algorithm for k-polygon graphs has performance ratio 2k(2) and runs in time O(n(3)).
We consider to design approximation algorithms for the survivable network design problem in hypergraphs (SNDPHG) based on algorithms developed for the survivable network design problem in graphs (SNDP) or the element ...
详细信息
We consider to design approximation algorithms for the survivable network design problem in hypergraphs (SNDPHG) based on algorithms developed for the survivable network design problem in graphs (SNDP) or the element connectivity problem in graphs (ECP). Given an instance of the SNDPHG. by replacing each hyperedge e = {v(1),...,v(k)} with a new vertex omega(e) and k edges {omega(e),nu(1)},...,{omega(e),nu(k)} we define an SNDP or ECP in the resulting graph. We show that by approximately solving the. SNDP or ECP defined in this way, several approximation algorithms for the SNDPHG can be obtained. One of our results is a d(max)(+)-approximation algorithm for the SNDPHG with d(max) less than or equal to 3, where d(max) (resp. d(max)(+)) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a d(max)(+)H(r(max))-approximation algorithm for the SNDPHG, where H(i) = Sigma(j=1)(l) 1/j is the harmonic function and r(max) is the maximum connectivity requirement.
We present a new class of randomized approximation algorithms for unrelated parallel machine scheduling problems with the average weighted completion time objective. The key idea is to assign jobs randomly to machines...
详细信息
We present a new class of randomized approximation algorithms for unrelated parallel machine scheduling problems with the average weighted completion time objective. The key idea is to assign jobs randomly to machines with probabilities derived from an optimal solution to a linear programming (LP) relaxation in time-indexed variables. Our main results are a (2+epsilon)-approximation algorithm for the model with individual job release dates and a (3/2+epsilon)-approximation algorithm if all jobs are released simultaneously. We obtain corresponding bounds on the quality of the LP relaxation. It is an interesting implication for identical parallel machine scheduling that jobs are randomly assigned to machines;in which each machine is equally likely. In addition, in this case the algorithm has running time O(n log n) and performance guarantee 2. Moreover, the approximation result for identical parallel machine scheduling applies to the on-line setting in which jobs arrive over time as well, with no difference in performance guarantee.
The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a ca...
详细信息
The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity *** goal is to find a subset of items of maximum profit such that they have a feasible packing in the ***(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems *** paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .
In wireless communication, the signal of a typical broadcast station is transmitted from a broadcast center p and reaches objects at a distance, say, r from it. In addition there is a radius r 0 , r 0 < r, such tha...
详细信息
In wireless communication, the signal of a typical broadcast station is transmitted from a broadcast center p and reaches objects at a distance, say, r from it. In addition there is a radius r 0 , r 0 < r, such that the signal originating from the center of the station is so strong that human habitation within distance r 0 from the center p should be avoided. In other words, points within distance r 0 from the station comprise a hazardous zone. We consider the following station layout proble: Cover a given planar region that includes a collection of buildings with a minimum number of stations so that every point in the region is within the reach of a station, while at the same time no interior point of any building is within the hazardous zone of a station. We give algorithms for computing such station layouts in both the one- and two-dimensional cases.
We deal with a single machine scheduling problem in which each job has a release date, a delivery time and a controllable processing time. The fact that the jobs have a controllable processing time means that it is al...
详细信息
We deal with a single machine scheduling problem in which each job has a release date, a delivery time and a controllable processing time. The fact that the jobs have a controllable processing time means that it is allowed to compress (a part of) the processing time of the job, in return for compression cost. The objective is to find a schedule that minimizes the total cost, that is, the latest delivery time of any job plus the total compression cost. In this note we discuss how the techniques of Hall and Shmoys [3] and Hall [1] can directly be applied to design a polynomial time approximation scheme for this problem.
Recently there has been a surge of interest in auctions research triggered on the one hand by auctions of bandwidth and other public assets and on the other by the popularity of Internet auctions and the possibility o...
详细信息
ISBN:
(纸本)3540424709
Recently there has been a surge of interest in auctions research triggered on the one hand by auctions of bandwidth and other public assets and on the other by the popularity of Internet auctions and the possibility of new auction formats enabled by e-commerce. Simultaneous auction of items is a popular auction format. We consider the problem of maximizing total revenue in the simultaneous auction of a set of items where the bidders have individual budget constraints. Each bidder is permitted to bid on all the items of his choice and specifies his budget constraint to the auctioneer, who must select bids to maximize the revenue while ensuring that no budget constraints are violated. We show that the problem of maximizing revenue is such a setting is NP-hard, and present a factor-1.62 approximation algorithm for it. We formulate the problem as an integer program and solve a linear relaxation to obtain a fractional optimal solution, which is then deterministically rounded to obtain an integer solution. We argue that the loss in revenue incurred by the rounding procedure is bounded by a factor of 1.62.
The uncapacitated facility location problem in the following formulation is considered: max(S subset of or equal to I) Z(S) = Sigma(j is an element of J)max(i is an element of S)b(ij) - Sigma(i is an element of S)c(i)...
详细信息
The uncapacitated facility location problem in the following formulation is considered: max(S subset of or equal to I) Z(S) = Sigma(j is an element of J)max(i is an element of S)b(ij) - Sigma(i is an element of S)c(i), where I and J are finite sets, and b(ij), c(i)greater than or equal to 0 are rational numbers. Let Z* denote the optimal value of the problem and let Z(R) = Sigma(j is an element of J)min(i is an element of I)b(ij) - Sigma(i is an element of I)c(i). Cornuejols et al. (Ann. Discrete Math. 1 (1977) 163-178) prove that for the problem with the additional cardinality constraint \S\less than or equal to K, a simple greedy algorithm finds a feasible solution S such that (Z(S) - ZR)/(Z* - ZR)greater than or equal to 1 - e(-1) approximate to 0.632. We suggest a polynomial-time approximation algorithm for the unconstrained version of the problem, based on the idea of randomized rounding due to Goemans and Williamson (SIAM J. Discrete Math. 7 (1994) 656 - 666). It is proved that the algorithm delivers a solution S such that (Z(S) - Z(R))/(Z* - Z(R))greater than or equal to 2(root 2 - 1) approximate to 0.828. We also show that there exists epsilon > 0 such that it is NP-hard to find an approximate solution S with (Z(S) - Z(R))/(Z* - Z(R))greater than or equal to 1 - epsilon. (C) 1999 Elsevier Science B.V. All rights reserved.
In the k-level uncapacitated facility location problem, we have a set of demand points where clients are located. The demand of each client is known. Facilities have to be located at given sites in order to service th...
详细信息
In the k-level uncapacitated facility location problem, we have a set of demand points where clients are located. The demand of each client is known. Facilities have to be located at given sites in order to service the clients, and each client is to be serviced by a sequence of k different facilities, each of which belongs to a distinct level. There are no capacity restrictions on the facilities. There is a positive fixed cost of setting up a facility, and a per unit cost of shipping goods between each pair of locations. We assume that these distances are all nonnegative and satisfy the triangle inequality. The problem is to find an assignment of each client to a sequence of k facilities, one at each level, so that the demand of each client is satisfied, for which the sum of the setup costs and the service costs is minimized. We develop a randomized algorithm for the k-level facility location problem that is guaranteed to find a feasible solution of expected cost within a factor of 3 of the optimum cost. The algorithm is a randomized rounding procedure that uses an optimal solution of a linear programming relaxation and its dual to make a random choice of facilities to be opened. We show how this algorithm can be derandomized to yield a 3-approximation algorithm. (C) 1999 Elsevier Science B.V. All rights reserved.
暂无评论