In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vert...
详细信息
In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vertex cover problem with submodular *** are given a cost graph and an *** problem determines a vertex set such that covers at least *** objective is to minimize the total cost of the vertices in plus the penalty of the uncovered edge set,where the penalty is determined by a submodular *** design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the *** the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor *** the submodular penalty cost function is linear,the approximation factor of the proposed algorithm is reduced to,which is the best factor if the unique game conjecture holds.
Emphasis on effective demand management is becoming increasingly recognized as an important factor in operations performance as well as the supply management. One of the known leverages to demand management is pricing...
详细信息
Emphasis on effective demand management is becoming increasingly recognized as an important factor in operations performance as well as the supply management. One of the known leverages to demand management is pricing. In joint pricing and production planning problem, manufacturer or supplier faces a price-sensitive demand and it should maximize its profit by making decision on the production policy among the finite time horizon while predicting the demand via determination of the prices of the products it sells. In this paper, a single-item joint pricing and production planning with concave revenue function has been discussed. By a piecewise linear approximation and reduction of the resulting problem to a bilinear one, an effective heuristic procedure has been proposed to solve it optimally. The efficiency of the procedure has been shown by numerical experiments.
Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions. Namely, given any two permutations, find the shortest distance between them. This problem is r...
详细信息
Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions. Namely, given any two permutations, find the shortest distance between them. This problem is related with genome rearrangement. The sorting of signed permutations is studied. Because in genome rearrangement, genes are oriented in DNA sequences. The transpositions which have been studied in the literature can be viewed as operations working on two consecutive segments of the genome. In this paper, a new kind of transposition which can work on two arbitrary segments of the genome is proposed, and the sorting of signed permutations by reversals and this new kind of transpositions are studied. After establishing a lower bound on the number of operations needed, a 2-approximation algorithm is presented for this problem and an example is given to show that the performance ratio of the algorithm cannot be improved.
In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable *** objective is to find a transportation scheme to minimize the longest distance travel...
详细信息
In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable *** objective is to find a transportation scheme to minimize the longest distance traveled by a single vehicle such that all the customers are served without violating the capacity *** authors show that this problem has no polynomialtime algorithm with performance ratio less than 2 on condition that P≠NP,and then provide a 2-approximation algorithm.
We consider the problem of releasing multiple types of jobs to a facility over a fixed period. In the problem, each type of job has its own demand for the period and the daily capacity of the facility can fluctuate. T...
详细信息
We consider the problem of releasing multiple types of jobs to a facility over a fixed period. In the problem, each type of job has its own demand for the period and the daily capacity of the facility can fluctuate. The variability of each type is defined as the total absolute deviation between the number of jobs of the corresponding type released on consecutive days. The objective is to minimize the total variability over all types. We show that the problem is strongly NP-hard. In addition, we develop an approximation algorithm and analyze its approximability according to the level of fluctuation of the daily capacity. (C) 2012 Elsevier B.V. All rights reserved.
Different from the classical k-means problem, the functional k means problem involves a kind of dynamic data, which is generated by continuous processes. In this paper, we mainly design an O(ln k)-approximation algori...
详细信息
Different from the classical k-means problem, the functional k means problem involves a kind of dynamic data, which is generated by continuous processes. In this paper, we mainly design an O(ln k)-approximation algorithm based on the seeding method for functional k-means problem. Moreover, the numerical experiment presented shows that this algorithm is more efficient than the functional k-means clustering algorithm.
This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set , a collection of sets , a weight function on , a cost function on , a connected gr...
详细信息
This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set , a collection of sets , a weight function on , a cost function on , a connected graph (called communication graph) on vertex set , and a budget , the MWBCSC problem is to select a subcollection such that the cost , the subgraph of induced by is connected, and the total weight of elements covered by (that is ) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio , where is the maximum degree of graph and is the number of sets in . In particular, if every set has cost at most , the performance ratio can be improved to .
There is an error in our paper "An approximation algorithm fur Minimum-Cost Vertex-Connectivity Problems" (algorithmica (1997), 18:21-43). In that paper we considered the following problem: given an undirect...
详细信息
There is an error in our paper "An approximation algorithm fur Minimum-Cost Vertex-Connectivity Problems" (algorithmica (1997), 18:21-43). In that paper we considered the following problem: given an undirected graph and values r(ij) for each pair of vertices i and j, find a minimum-cost set of edged, such that there are r(ij) vertex-disjoint paths between vertices i and j. We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal-dual approach which has led to approximation El algorithms for many edge-connectivity problems, The algorithms work in a series of stages;in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case r(ij) = k for all i, j, we described a polynomial-time algorithm that claimed to output a solution of cost no more than 27-l(k) times optimal, where H(n) 1 + 1/2 + ... + 1/n. This result is erroneous. We describe an example where our primal-dual augmentation subroutine, when augmenting a k-vertex connected graph to a (k + 1)-vertex connected graph, gives solutions that are a factor n (k) away from the minimum, In the case r(ij) is an element of {0, 1, 2} for all i, j, we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k-vertex connected case does hold, and that the algorithm performs as claimed.
Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling...
详细信息
Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling cost by vehicles. We give differential approximation algorithms for the fleet size and mix vehicle routing problem （FSMVRP） with two kinds of vehicles, the capacities of which are respectively nlk and n2k, n2 〉 nl ≥ 1, k ≥ 1. Using existing theories for vehicle routing problems and feature of the algorithms represented in the paper, we also prove that the algorithms give（1-6n＋3/（n＋1）2k＋n＋1）differential approximation ratio for （k, nk） VRP, n 〉 1and （1-6n2＋3n/n1k＋n2k）2k）differential approximation ratio for （nlk, n2k）VRP, n2 〉 nl 〉 1.
In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For eac...
详细信息
In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For each client-facility pair, there is an unit service cost to serve the client with unit demand by the facility. The total demands served by a facility cannot exceed the uniform capacity. We want to open at most k facilities to serve all the demands of the clients without violating the capacity constraint such that the total opening and serving cost is minimized. The main contribution of this work is to present the first combinatorial bi-criteria approximation algorithm for the UC-k-FLP by violating the cardinality constraint.
暂无评论