In this paper we study several instances of the aligned k-center problem where the goal is, given a set of points S in the plane and a parameter k >= 1, to find k disks with centers on a line l such that their unio...
详细信息
In this paper we study several instances of the aligned k-center problem where the goal is, given a set of points S in the plane and a parameter k >= 1, to find k disks with centers on a line l such that their union covers S and the maximum radius of the disks is minimized. This problem is a constrained version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, or a polygon. We first consider the simplest version of the problem where the line I: is given in advance;we can sole this problem in time O(n log(2) n). In the case where only the direction of is fixed, we give an O(n(2) log(2) n)-time algorithm. When l is an arbitrary line, we give a randomized algorithm with expected running time O(n(4) log(2) n). Then we present (1+epsilon)-approximation algorithms for these three problems. When we denote T (k, epsilon) = (k/epsilon(2)+(k/epsilon) log k) log(1/epsilon), these algorithms run in O(n log k+T (k, epsilon)) time, O(n log k vertical bar T(k. epsilon)/epsilon) time, and O(n log k vertical bar T(k. epsilon)/epsilon(2)) time, respectively. For k = O(n(1/ 3) / log n), we also give randomized algorithms with expected running times O(n + (k/epsilon(2)) log(1/epsilon)), O(n + (k/epsilon(3)) log(1/epsilon)), and O(n + (k/epsilon(4)) log(1/epsilon)), respectively.
A novel approach that integrates occlusion culling within the view-dependent rendering framework is proposed. The algorithm uses the prioritized-layered projection（PLP） algorithm to occlude those obscured objects, a...
详细信息
A novel approach that integrates occlusion culling within the view-dependent rendering framework is proposed. The algorithm uses the prioritized-layered projection（PLP） algorithm to occlude those obscured objects, and uses an approximate visibility technique to accurately and efficiently determine which objects will be visible in the coming future and prefetch those objects from disk before they are rendered, view-dependent rendering technique provides the ability to change level of detail over the surface seamlessly and smoothly in real-time according to cell solidity value.
In sensorless driving of permanent-magnet synchronous motors, it is difficult to deal with the nonlinear characteristic of the magnetic circuit and the harmonies of magnetic density distribution in the air gap. Using ...
详细信息
In sensorless driving of permanent-magnet synchronous motors, it is difficult to deal with the nonlinear characteristic of the magnetic circuit and the harmonies of magnetic density distribution in the air gap. Using a neural network has been considered to be a powerful tool but, unfortunately, only few simulation-based works can be found. In this paper, an experiment system and successful experiment results using our proposed sensorless driving method of permanent-magnet synchronous motors based on neural networks will be presented. The method estimates the position errors from electromotive force instead of directly estimating the position using neural networks and then using the approximate algorithm to obtain the rotor position. Experiment results show that the method has excellent possibility in practical applications.
This article is intended to present a multiple choice knapsack problem with fuzzy coefficients. We propose an approximate algorithm for solving the problem and obtaining some non-dominated approximate solutions. In th...
详细信息
This article is intended to present a multiple choice knapsack problem with fuzzy coefficients. We propose an approximate algorithm for solving the problem and obtaining some non-dominated approximate solutions. In the interpretation of the constraints, the degree satisfying the inequality between fuzzy numbers is defined on the basis of the agreement index. Finally, a numerical example is shown.
The paper analyzes the influence, exerted by the mutual relations of deadline intervals on behavior of the optimal solution values for the random Sequencing Jobs with Deadlines (SJD) problems. An asymptotically sub-op...
详细信息
The paper analyzes the influence, exerted by the mutual relations of deadline intervals on behavior of the optimal solution values for the random Sequencing Jobs with Deadlines (SJD) problems. An asymptotically sub-optimal algorithm is proposed. It is assumed that the problem coefficients are realizations of independent uniformly distributed random variables and deadlines are deterministic. The results, presented in the paper, significantly extend knowledge on behavior of the optimal solutions to the SJD problem in the asymptotical case. (C) 2017 Elsevier B.V. All rights reserved.
The research in parallel machine scheduling in combinatorial optimization suggests that the desirable parallel efficiency could be achieved when the jobs are sorted in the non-increasing order of processing times. In ...
详细信息
The research in parallel machine scheduling in combinatorial optimization suggests that the desirable parallel efficiency could be achieved when the jobs are sorted in the non-increasing order of processing times. In this paper, we find that the time spending for computing the permanent of a sparse matrix by hybrid algorithm is strongly correlated to its permanent value. A strategy is introduced to improve a parallel algorithm for sparse permanent. Methods for approximating permanents, which have been studied extensively, are used to approximate the permanent values of submatrices to decide the processing order of jobs. This gives an improved load balancing method. Numerical results show that the parallel efficiency is improved remarkably for the permanents of fullerene graphs, which are of great interests in nanoscience. Copyright (c) 2012 John Wiley & Sons, Ltd.
An approximate algorithm for solving pure interger problems is examined. The algorithm belongs to the class of component algorithms using feasible integer directions. The basic characteristics of the algorithm are ana...
详细信息
An approximate algorithm for solving pure interger problems is examined. The algorithm belongs to the class of component algorithms using feasible integer directions. The basic characteristics of the algorithm are analyzed. Testing on an IBM/PC/AT personal computer is carried out. The proposed algorithm is compared with other well known approximate algorithms
A new formulation of the reverse bin-packing problem is suggested. One distinct feature of the new formulation is that it takes into account of a decision-maker's preferences for a set of objects that are evaluate...
详细信息
A new formulation of the reverse bin-packing problem is suggested. One distinct feature of the new formulation is that it takes into account of a decision-maker's preferences for a set of objects that are evaluated by multiple quality criteria. The aspects of this problem are discussed that relate to the theory of multiple criteria decision making. The known methods for solving the classic and the reverse bin-packing problems (the multiple knapsack problem) are reviewed.
To construct the asymptotically optimum plan of the p-index axial assignment problem of order n, p algorithms a(0) , a(1) ,..., a(p-1) with complexities equal to O(n(p+1)), O( n(p)),..., O(n(2))operations, respectivel...
详细信息
To construct the asymptotically optimum plan of the p-index axial assignment problem of order n, p algorithms a(0) , a(1) ,..., a(p-1) with complexities equal to O(n(p+1)), O( n(p)),..., O(n(2))operations, respectively, are proposed and substantiated under some additional conditions imposed on the coefficients of the objective function.
Community detection is one way to reduce the complexity of analyzing networks, especially with their rapid growth. Dividing networks into communities can help analysts and experts to understand the behavior and functi...
详细信息
Community detection is one way to reduce the complexity of analyzing networks, especially with their rapid growth. Dividing networks into communities can help analysts and experts to understand the behavior and function of the networks. Also, besides the community structure, finding the influential nodes to spread infor-mation in the networks is a critical issue for researchers. Community detection is a challenging topic in network science and, various methods have been proposed for that. Many methods that find community structure use modularity as a measure to qualify the strength of community structure. These methods try to find community structures based on maximizing modularity. Modularity maximization is an NP-hard problem. One of the ap-proaches that could solve such problems is approximate algorithms. Identifying the influential nodes which has many applications in complex networks can also be used in community detection. Therefore to maximize the modularity, in this paper, we first try to identify influential nodes, and then by estimating their influence domain, the communities are detected. We used scale-free networks concepts to prove the approximate factor. Experi-ments on real-world networks show that the proposed algorithm can compete with the state-of-the-art methods in community detection algorithms. In addition, our proposed method also identifies the most influential node within each community.
暂无评论