The segment minimization problem consists of representing an integer matrix as the sum of the fewest number of integer matrices each of which have the property that the non-zeroes in each row are consecutive. This has...
详细信息
The segment minimization problem consists of representing an integer matrix as the sum of the fewest number of integer matrices each of which have the property that the non-zeroes in each row are consecutive. This has direct applications to an effective form of cancer treatment. Using several insights, we extend previous results to obtain constant-factor improvements in the approximation guarantees. We show that these improvements yield better performance by providing an experimental evaluation of all known approximation algorithms using both synthetic and real-world clinical data. Our algorithms are superior for 76% of instances and we argue for their utility alongside the heuristic approaches used in practice. (C) 2010 Elsevier B.V. All rights reserved.
We construct new approximation algorithms for MAX SET SPLITTING and MAX NOT-ALL-EQUAL SAT which when combined with existing algorithms give the best approximation results so far for these problems. Furthermore, we sol...
详细信息
We construct new approximation algorithms for MAX SET SPLITTING and MAX NOT-ALL-EQUAL SAT which when combined with existing algorithms give the best approximation results so far for these problems. Furthermore, we solve a linear program to find an upper bound on the performance ratio. This linear program can also be used to see which of the contributing algorithms it is possible to exclude from the combined algorithm without affecting its performance ratio. (C) 1998 Elsevier Science B.V.
In this paper we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given areas s(1), s(2), ... s(p) (such that Sigma(i=l)(p) s(i) = l...
详细信息
In this paper we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given areas s(1), s(2), ... s(p) (such that Sigma(i=l)(p) s(i) = l),so as to minimize either (i) the sum of the p perimeters of the rectangles or (ii) the largest perimeter of the p rectangles? For both problems, we prove NP-completeness and we introduce a 7/4-approximation algorithm for (i) and a 4 (2/root3)-approximation algorithm for (ii).
In this paper, we give randomized approximation algorithms for stochastic cumulative VRPs for the split and unsplit deliveries. The approximation ratios are max{1 + 1.5 alpha, 3} and 6, respectively, where a is the ap...
详细信息
In this paper, we give randomized approximation algorithms for stochastic cumulative VRPs for the split and unsplit deliveries. The approximation ratios are max{1 + 1.5 alpha, 3} and 6, respectively, where a is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees. These results extend the results in Anupam Gupta et al. (2012) and Daya Ram Gaur et al. (2013). The bounds reported here improve the bounds in Daya Ram Gaur et al. (2016). (C) 2018 Elsevier B.V. All rights reserved.
In this paper, we present a new bicriteria approximation algorithm for the degree-bounded minimum spanning tree problem. I this problem, we are given an undirected graph, a nonnegative cost function on the edges, and ...
详细信息
In this paper, we present a new bicriteria approximation algorithm for the degree-bounded minimum spanning tree problem. I this problem, we are given an undirected graph, a nonnegative cost function on the edges, and a positive integer B, and the goal is to find a minimum-cost spanning tree T with maximum degree at most B*. In an n-node graph, our algorithm finds a spanning tree with maximum degree O (B* + log n) and cost O (opt B*), where opt B* is the minimum cost of any spanning tree whose maximum degree is at most B* Our algorithm uses ideas from Lagrangean duality. We show how a set of optimum Lagrangean multipliers yields bounds on both the degree and the cost of the computed solution.
Efficient construction of large-scale linkage maps is highly desired in current gene mapping projects. To evaluate the performance of available approaches in the literature, four published methods, the insertion (IN),...
详细信息
Efficient construction of large-scale linkage maps is highly desired in current gene mapping projects. To evaluate the performance of available approaches in the literature, four published methods, the insertion (IN), seriation (SER), neighbor mapping (NM), and unidirectional growth (UG) were compared on the basis of simulated F(2) data with various population sizes, interferences, missing genotype rates, and mis-genotyping rates. Simulation results showed that the IN method outperformed, or at least was comparable to, the other three methods. These algorithms were also applied to a real data set and results showed that the linkage order obtained by the IN algorithm was superior to the other methods. Thus, this study suggests that the IN method should be used when constructing large-scale linkage maps.
作者：
Fujii, KaitoKyoto Univ
Grad Sch Informat Sakyo Ku 36-1 Yoshida Honmachi Kyoto 6068501 Japan
Maximizing a monotone submodular function subject to a b-matching constraint is increasing in importance due to its application to the content spread maximization problem, but few practical algorithms are known other ...
详细信息
Maximizing a monotone submodular function subject to a b-matching constraint is increasing in importance due to its application to the content spread maximization problem, but few practical algorithms are known other than the greedy algorithm. The best approximation scheme so far is the local search algorithm, proposed by Feldman, Naor, Schwartz, and Ward [8] (2011). It obtains a 1/(2 + 1/k + is an element of)-approximate solution for an arbitrary positive integer k and positive real number is an element of. For graphs with n vertices and m edges, the running time of the local search algorithm is O(b(k+1) (Delta - 1)(k)nm is an element of(-1)) where Delta is the maximum degree, which is impractical for large problems. In this paper, we present two new algorithms for this problem. One is a find walk algorithm that runs in O(bm) time and achieves 1/4-approximation. It is faster than the greedy algorithm whose approximation ratio is 1/3. The other one is a randomized local search algorithm that is a faster variant of the local search algorithm. In expectation, it runs in O(b(k+1) (Delta - 1)(k-1)m log 1/is an element of) time and obtains a (1/(2 + 1/k) - is an element of)-approximate solution. (C) 2016 Elsevier B.V. All rights reserved.
We consider the uncapacitated facility location problem. In this problem, there is a set of locations at which facilities can be built;a fixed cost f(i) is incurred if a facility is opened at location i. Furthermore, ...
详细信息
We consider the uncapacitated facility location problem. In this problem, there is a set of locations at which facilities can be built;a fixed cost f(i) is incurred if a facility is opened at location i. Furthermore, there is a set of demand locations to be serviced by the opened facilities;if the demand location j is assigned to a facility at location i, then there is an associated service cost proportional to the distance between i and j, c(ij). The objective is to determine which facilities to open and an assignment of demand points to the opened facilities, so as to minimize the total cost. We assume that the distance function c is symmetric and satisfies the triangle inequality. For this problem we obtain a (1 + 2/e)-approximation algorithm, where 1 + 2/e approximate to 1.736, which is a significant improvement on the previously known approximation guarantees. The algorithm works by rounding an optimal fractional solution to a linear programming relaxation. Our techniques use properties of optimal solutions to the linear program, randomized rounding, as well as a generalization of the decomposition techniques of Shmoys, Tardos, and Aardal [Proceedings of the 29th ACM Symposium on Theory of Computing, El Paso, TX, 1997, pp. 265-274].
The projection games (aka Label Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover. In ...
详细信息
The projection games (aka Label Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover. In this paper we design several approximation algorithms for projection games: (1) A polynomial-time approximation algorithm that improves on the previous best approximation by Charikar et al. (Algorithmica 61(1):190-206, 2011). (2) A sub-exponential time algorithm with much tighter approximation for the case of smooth projection games. (3) A polynomial-time approximation scheme (PTAS) for projection games on planar graphs and a tight running time lower bound for such approximation schemes. The conference version of this paper had only the PTAS but not the running time lower bound.
In this paper we consider the two-stage stochastic linear assignment (2SSLA) problem, which is a stochastic extension of the classical deterministic linear assignment problem. For each agent and job, the decision make...
详细信息
In this paper we consider the two-stage stochastic linear assignment (2SSLA) problem, which is a stochastic extension of the classical deterministic linear assignment problem. For each agent and job, the decision maker has to decide whether to make assignments now or to wait for the second stage. Assignments of agents and jobs, for which decisions are delayed to the second stage, are then completed based on the scenario realized. We discuss two greedy approximation algorithms from the literature and derive a simple necessary optimality condition that generalizes the key ideas behind both of these approaches. Subsequently, based on this result we design a new greedy approximation method. Theoretical observations and the results of computational experiments are also presented.
暂无评论