The problem of integrated production and transportation scheduling, commonly faced by make-to-order manufacturers under a commit-to-delivery business mode, is known to be strongly NP-hard. In this study, we propose tw...
详细信息
The problem of integrated production and transportation scheduling, commonly faced by make-to-order manufacturers under a commit-to-delivery business mode, is known to be strongly NP-hard. In this study, we propose two new exactalgorithms to solve the problem with order acceptance decisions also taken into account. These algorithms can achieve polynomial or pseudo-polynomial running times in several practical situations. We also develop the first pseudo-polynomial time approximation scheme for this problem. It not only guarantees a worst-case performance ratio of (1 + c) for any fixed c > 0 , but also achieves good computational performance.(c) 2022 Elsevier B.V. All rights reserved.
In a sensor network, data might be stored in so-called storage nodes, which receive raw data from other nodes, compress them, and send them toward a sink. We consider the problem of locating k storage nodes in order t...
详细信息
In a sensor network, data might be stored in so-called storage nodes, which receive raw data from other nodes, compress them, and send them toward a sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging the raw data to the storage nodes as well as to converge the compressed data to the sink. This is known as the minimum k-storage problem. In general, the problem is NP-hard. However, we are able to devise a polynomial-time algorithm that optimally solves the problem in bounded-tree width graphs. We then characterize the minimum k-storage problem from the approximation viewpoint. We first prove that it is NP-hard to be approximated within a factor smaller than 1 + 1/e. We then propose a local search algorithm that guarantees a constant approximation factor. We conducted extended experiments to show that the algorithm performs very well, exhibiting very small deviation from the optimum and computational time. It is worth to note that our problem is a generalization to the well-known metric k-median problem and then the obtained results also hold for this case.
We handle in this paper three dominating clique problems, namely, the decision problem to detect whether a graph has a dominating clique and two optimization versions asking to compute a maximum- and a minimum-size do...
详细信息
We handle in this paper three dominating clique problems, namely, the decision problem to detect whether a graph has a dominating clique and two optimization versions asking to compute a maximum- and a minimum-size dominating clique of a graph G, if G has a dominating clique. For the three problems we propose exact moderately exponential algorithms with worst-case running time upper bounds improving those by Kratsch and Liedloff [D. Kratsch, M. Liedloff, An exact algorithm for the minimum dominating clique problem, Theoret. Comput. Sci. 385 (1-3) (2007) 226-240]. We then study the three problems in sparse and dense graphs also providing improved running time upper bounds. Finally, we propose some exponential time approximationalgorithms for the optimization versions. (C) 2012 Elsevier B.V. All rights reserved.
Anomaly detection problems (also called change-point detection problems) have been studied in data mining, statistics and computer science over the last several decades (mostly in non-network context) in applications ...
详细信息
Anomaly detection problems (also called change-point detection problems) have been studied in data mining, statistics and computer science over the last several decades (mostly in non-network context) in applications such as medical condition monitoring, weather change detection and speech recognition. In recent days, however, anomaly detection problems have become increasing more relevant in the context of network science since useful insights for many complex systems in biology, finance and social science are often obtained by representing them via networks. Notions of local and non-local curvatures of higher-dimensional geometric shapes and topological spaces play a fundamental role in physics and mathematics in characterizing anomalous behaviours of these higher dimensional entities. However, using curvature measures to detect anomalies in networks is not yet very common. To this end, a main goal in this paper to formulate and analyze curvature analysis methods to provide the foundations of systematic approaches to find critical components and detect anomalies in networks. For this purpose, we use two measures of network curvatures which depend on non-trivial global properties, such as distributions of geodesics and higher-order correlations among nodes, of the given network. Based on these measures, we precisely formulate several computational problems related to anomaly detection in static or dynamic networks, and provide non-trivial computational complexity results for these problems. This paper must not be viewed as delivering the final word on appropriateness and suitability of specific curvature measures. Instead, it is our hope that this paper will stimulate and motivate further theoretical or empirical research concerning the exciting interplay between notions of curvatures from network and non-network domains, a much desired goal in our opinion.
Digital microfluidic biochips (DMFBs) are rectangular arrays of electrodes, or cells, that enable precise manipulation of nanoliter-sized droplets of biological fluids and chemical reagents. Because of the safety-crit...
详细信息
Digital microfluidic biochips (DMFBs) are rectangular arrays of electrodes, or cells, that enable precise manipulation of nanoliter-sized droplets of biological fluids and chemical reagents. Because of the safety-critical nature of their applications, biochips must be tested frequently, both off-line (e.g., postmanufacturing) and concurrent with assay execution. Under both scenarios, testing is accomplished by routing one or more test droplets across the chip and recording their arrival at the destination. In this paper, we formalize the DMFB-testing problem under the common objective of completion time minimization, including previously ignored constraints of droplet noninterference. Our contributions include a proof that the general version of the problem is NP-hard, tight lower bounds for both off-line and concurrent testing, optimal and approximationalgorithms for off-line testing of commonly used rectangular shaped biochips, as well as a concurrent testing heuristic producing solutions within 23%-34% of the lower bound in experiments conducted on data sets simulating varying percentages of biochip cells occupied by concurrently running assays.
In this paper, we are interested in producing discrete and tractable representations of the set of non dominated points for multi-objective optimization problems, both in the continuous and discrete cases. These repre...
详细信息
In this paper, we are interested in producing discrete and tractable representations of the set of non dominated points for multi-objective optimization problems, both in the continuous and discrete cases. These representations must satisfy some conditions of coverage, i.e. providing a good approximation of the non-dominated set, spacing, i.e. without redundancies, and cardinality, i.e. with the smallest possible number of points. This leads us to introduce the new concept of (epsilon, epsilon')-kernels, or epsilon-kernels when epsilon' = epsilon is possible, which correspond to epsilon=Pareto sets satisfying an additional. condition, of epsilon'-stability. Among these, the kernels of small, or possibly optimal, cardinality are claimed to be good representations of the non-dominated set. We first establish some general properties on epsilon-kernels. Then, for the bi-objective case, we propose some generic algorithms computing in polynomial time either an epsilon-kernel of small size or, for a fixed size k, an epsilon-kernel with a nearly optimal approximation ratio 1 + epsilon. For more than two objectives, we show that epsilon-kernels do not necessarily exist but that (epsilon, epsilon' )-kernels with epsilon' <= root 1 + epsilon-1 always exist. Nevertheless, we show that the size of a smallest (epsilon, epsilon')-kernel can be very far from the size of a smallest epsilon-Pareto set. (C) 2016 Published by Elsevier B.V.
暂无评论