A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a ...
详细信息
A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a 3K(2)-free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n(2)). These algorithms suppose that an HCA model of the graph is given. (c) 2006 Published by Elsevier B.V.
In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single ma...
详细信息
In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness 1aEuro-max-I T pound (j) and for the problem of maximizing the number of tardy jobs 1aEuro-maxI U pound (j) . In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem 1aEuro-max-I T pound (j) is polynomially solvable. For several special cases of problem 1aEuro-maxI T pound (j) , we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.
We consider the problem of utilizing a pack of m batteries serving n current demands in electric vehicles. When serving a demand, the current allocation might be split among the batteries in the pack. A battery's ...
详细信息
We consider the problem of utilizing a pack of m batteries serving n current demands in electric vehicles. When serving a demand, the current allocation might be split among the batteries in the pack. A battery's life depends on the discharge current used for supplying the requests. Any deviation from the optimal discharge-current is associated with a penalty. Thus, the problem is to serve an online sequence of current requests in a way that minimizes the total penalty associated with the service. We show that the offline problem, for which the sequence of current demands is known in advance, is strongly NP-hard and hard to approximate within an additive gap of omega(m) from the optimum. For the online problem, we present a competitive algorithm associated with the redundant penalty at most m. Finally, we provide a lower bound of 1.5 for the multiplicative competitive ratio of any online algorithm.
This paper deals with the problem of a logistics company that has to serve its customers by first putting the products on pallets and then loading the pallets into trucks. Besides the standard geometric constraints of...
详细信息
This paper deals with the problem of a logistics company that has to serve its customers by first putting the products on pallets and then loading the pallets into trucks. Besides the standard geometric constraints of products not overlapping each other and not exceeding the dimensions of pallets and trucks, in this real problem, there are many other constraints, related to the total weight of the load, the maximum weight supported by each axle, and the distribution of the load inside the truck. Although the problem can be decomposed into two phases, pallet loading and truck loading, we have taken a combined approach, building and placing pallets at the same time. For each position in the truck, a pallet is built and tailored for that position according to the constraints of height and weight. We have developed a GRASP algorithm, in which the constructive algorithmis randomized and an improvement phase is added to obtain high-quality solutions. The algorithm has been tested on two sets of real instances with different characteristics, involving up to 44 trucks. The results show that solutions with an optimal or near optimal number of trucks are obtained in very short computing times.
This paper addresses the integration of the PostgreSQL database management system (DBMS) with the Semantic Web. Integration algorithms based on the use of the DBMS capabilities that do not introduce changes in SQL are...
详细信息
This paper addresses the integration of the PostgreSQL database management system (DBMS) with the Semantic Web. Integration algorithms based on the use of the DBMS capabilities that do not introduce changes in SQL are proposed. An integration based on one of the algorithms supporting main formats of the Semantic Web is presented. The proposed algorithms can be implemented in different DBMSs supporting triggers (or rules), table functions, and indexing.
The problem of computing the intersection of parametric and algebraic curves arises in many applications of computer graphics and geometric and solid modeling. Previous algorithms are based on techniques from eliminat...
详细信息
The problem of computing the intersection of parametric and algebraic curves arises in many applications of computer graphics and geometric and solid modeling. Previous algorithms are based on techniques from elimination theory or subdivision and iteration and are typically limited to simple intersections of curves. Furthermore, algorithms based on elimination theory are restricted to low degree curves. This is mainly due to issues of efficiency and numerical stability. In this paper we use elimination theory and express the resultant of the equations of intersection as a matrix determinant. Using matrix computations the algorithm for intersection is reduced to computing eigenvalues and eigenvectors of matrices. We use techniques from linear algebra and numerical analysis to compute geometrically isolated higher order intersections of curves. Such intersections are obtained from tangential intersections, singular points, etc. The main advantage of the algorithm lies in its efficiency and robustness. The numerical accuracy of the operations is well understood and we come up with tight bounds on the errors using 64-bit IEEE floating point arithmetic. (C) 1995 Academic Press, Inc.
Building design is quite a complicated task with the design team trying to counterbalance various antagonistic parameters, which in turn are subject to various constraints. Due to this complexity, performance simulati...
详细信息
Building design is quite a complicated task with the design team trying to counterbalance various antagonistic parameters, which in turn are subject to various constraints. Due to this complexity, performance simulation tools are employed and as a consequence, optimization methods have just started being used, mainly as a decision aid. There are examples, amongst the architectural community, where probabilistic evolutionary algorithms or other derivative-free methods have been used with various decision variables and objective goals. This paper is a review of the methods and tools used for the building design optimization in an effort to explore the reasoning behind their selection, to present their abilities and performance issues and to identify the key characteristics of their future versions. (C) 2013 Elsevier Ltd. All rights reserved.
As die sizes are shrinking, and circuit complexities are increasing, the printed circuit board routing problem becomes more and more challenging. Traditional routing algorithms cannot handle these challenges effective...
详细信息
As die sizes are shrinking, and circuit complexities are increasing, the printed circuit board routing problem becomes more and more challenging. Traditional routing algorithms cannot handle these challenges effectively, and many high-end designs in the industry require manual routing efforts. This paper proposes a problem decomposition that distinguishes routing under dense components from routing in the intermediate area. In particular, it proposes an effective methodology to find the escape routing solution for multiple components simultaneously such that the number of crossings in the intermediate area is minimized. For this, the problem is modeled as a longest path with forbidden pairs problem, and two algorithms are proposed for it. The first is an exact polynomial-time algorithm that is guaranteed to find the maximal planar routing solution on one layer. The second is a randomized algorithm that has good scalability characteristics for large circuits. Then, these algorithms are used to assign the maximal subset of planar nets to each layer, and then the remaining nets are distributed at the end. This paper demonstrates the effectiveness of these algorithms through experiments on industrial circuits.
The emergence of monitoring applications has precipitated the need for Data Stream Management Systems (DSMSs), which constantly monitor incoming data feeds (through registered continuous queries), in order to detect e...
详细信息
The emergence of monitoring applications has precipitated the need for Data Stream Management Systems (DSMSs), which constantly monitor incoming data feeds (through registered continuous queries), in order to detect events of interest. In this article, we examine the problem of how to schedule multiple Continuous Queries (CQs) in a DSMS to optimize different Quality of Service (QoS) metrics. We show that, unlike traditional online systems, scheduling policies in DSMSs that optimize for average response time will be different from policies that optimize for average slowdown, which is a more appropriate metric to use in the presence of a heterogeneous workload. Towards this, we propose policies to optimize for the average-case performance for both metrics. Additionally, we propose a hybrid scheduling policy that strikes a fine balance between performance and fairness, by looking at both the average- and worst-case performance, for both metrics. We also show how our policies can be adaptive enough to handle the inherent dynamic nature of monitoring applications. Furthermore, we discuss how our policies can be efficiently implemented and extended to exploit sharing in optimized multi-query plans and multi-stream CQs. Finally, we experimentally show using real data that our policies consistently outperform currently used ones.
作者：
Mielenz, KDNIST
Radiometr Phys Div Gaithersburg MD 20899 USA
This paper summarizes the theory of Fresnel diffraction by plane rectangular and circular apertures with a view;toward numerical computations. Approximations found in the earlier literature, ind,now obsolete, have bee...
详细信息
This paper summarizes the theory of Fresnel diffraction by plane rectangular and circular apertures with a view;toward numerical computations. Approximations found in the earlier literature, ind,now obsolete, have been eliminated and replaced by algorithms suitable for use on a personal computer.
暂无评论