We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this w...
详细信息
We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this well-studied problem the Largest differencing method of Karmarkar and Karp outperforms other existing polynomial-time approximation algorithms from an average-case perspective. For m >= 3 the worst-case performance of the Largest differencing method has remained a challenging open problem. In this paper we show that the worst-case performance ratio is bounded between 4/3 - 1/3(m-1) and 4/3 - 1/3m. For fixed m we establish further refined bounds in terms of n.
We consider the problem of partitioning a set of n numbers into m subsets of cardinality k = [n/m] or [n/m ], such that the maximum subset sum is minimal. We show that the performance ratio of the differencing method ...
详细信息
We consider the problem of partitioning a set of n numbers into m subsets of cardinality k = [n/m] or [n/m ], such that the maximum subset sum is minimal. We show that the performance ratio of the differencing method of Karmarkar and Karp for solving this problem is at least 2 - Sigma(k-01)(i=0) ll/kl for any fixed k. We also build a mixed integer linear programming model (MILP) whose solution yields the performance ratio for any given k. For k <= 7 these MILP-instances can be solved with an exact MILP-solver. This results in a computer-assisted proof of the tightness of the aforementioned lower bound for k <= 7. For k > 7 we prove that 2 - 1/k-1 is an upper bound on the performance ratio, thereby leaving a gap with the lower bound of Theta(k-3), which is less than 0.4%. (C) 2011 Elsevier B.V. All rights reserved.
The algorithm LDM (largest differencing method) divides a list of n random items into two blocks. The parameter of interest is the expected difference between the two block sums. It is shown that if the items are i.i....
详细信息
The algorithm LDM (largest differencing method) divides a list of n random items into two blocks. The parameter of interest is the expected difference between the two block sums. It is shown that if the items are i.i.d. and uniform then the rate of convergence of this parameter to zero is n(-Theta(log n)). An algorithm for balanced partitioning is constructed, with the same rate of convergence to zero.
The Max-Cut problem is a classical NP-hard problem where the objective is to partition the nodes of an edge-weighted graph in a way that maximizes the sum of edges between the parts. We present a greedy heuristic for ...
详细信息
The Max-Cut problem is a classical NP-hard problem where the objective is to partition the nodes of an edge-weighted graph in a way that maximizes the sum of edges between the parts. We present a greedy heuristic for solving Max-Cut that combines an Edge-Contraction heuristic with the differencing method. We compare the heuristic's performance to other greedy heuristics using a large and diverse set of problem instances. (C) 2021 Elsevier B.V. All rights reserved.
A commonly used semiparametric model is considered. We adopt two difference based estimators of the linear component of the model and propose corresponding thresholding estimators that can be used for variable selecti...
详细信息
A commonly used semiparametric model is considered. We adopt two difference based estimators of the linear component of the model and propose corresponding thresholding estimators that can be used for variable selection. For each thresholding estimator, variable selection in the linear component is developed and Consistency of the variable selection procedure is shown. We evaluate our method in a simulation study and implement it on a real data set. (C) 2013 Elsevier B.V. All rights reserved.
The problem of direction-of-arrival (DOA) estimation of quasi-stationary signals using a nested array in unknown noise field is investigated and two methods based on differencing method and eigenspace are proposed in ...
详细信息
ISBN:
(纸本)9781538647523
The problem of direction-of-arrival (DOA) estimation of quasi-stationary signals using a nested array in unknown noise field is investigated and two methods based on differencing method and eigenspace are proposed in this paper. Through performing differencing between the virtual received data, the unknown noise component is directly removed from the data model. The resulting data model is then utilized to find out the DOAs of the signals based on the theory of subspace. Thanks to the configuration of the nested array, it can produce large degrees of freedom (DOF) in the virtual sensor array which provides the virtual received data. These increased DOF can contribute enhanced resolution in DOA estimation. Numerical simulations of DOA estimation exhibit the effectiveness and superiority of the proposed methods.
This study used data from 1870 to 2008 to test the role of logistic regression models in predicting financial crises. This article first dealt with missing values in the data and removed time trends. Then, logistic re...
详细信息
This study used data from 1870 to 2008 to test the role of logistic regression models in predicting financial crises. This article first dealt with missing values in the data and removed time trends. Then, logistic regression models were used to predict and explore the occurrence of financial crises. During the exploration process, this article adopted principal component analysis and the method of eliminating multicollinearity interference for model optimization, and ultimately found that the area under the curve(AUC) in logistic regression was the highest, at 0.86. This indicates that logistic regression models provide more reliable predictions for financial crises. Based on the results, we further speculate that the total asset value and GDP are very important factors determining whether a financial crisis will occur. While there is room for improvement, the conclusion for this study still provides valuable insights into the connection between financial crises and specific banking factors.
暂无评论