24 research outputs found
An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem
No full textIn the k-median problem, given a set of locations, the goal is to select a subset of at most k centers so as to minimize the total cost of connecting each location to its nearest center. We study the uniform hard capacitated version of the k-median problem, in which each selected center can only serve a limited number of locations.
Inspired by the algorithm of Charikar, Guha, Tardos and Shmoys,
we give an improved approximation algorithm for this problem with increasing the capacities by a constant factor, which improves the previous best approximation algorithm proposed by Byrka, Fleszar, Rybicki and Spoerhase
Improved Approximation Algorithm for <em class="EmphasisTypeItalic">k</em>-level Uncapacitated Facility Location Problem (with Penalties)
No full textWe study the k-level uncapacitated facility location problem (k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most αk times OPT, where αk is an increasing function of k, with limk→∞αk=3. Our algorithm rounds a fractional solution to an extended LP formulation of the problem. The rounding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA’98) originally used for the group Steiner tree problem. We improve the approximation ratio for k-level UFL for all k ≥ 3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for k = 3,4, and 5. Second, we give a simple interpretation of the randomization process (Li ICALP’2011) for 1-level UFL in terms of solving an auxiliary (factor revealing) LP. Armed with this simple view point, we exercise the randomization on our algorithm for the k-level UFL. We further improve the approximation ratio for all k ≥ 3, obtaining 1.97, 2.09, and 2.19 for k = 3,4, and 5. Third, we extend our algorithm to the k-level UFL with penalties (k-level UFLWP), in which the setting is the same as k-level UFL except that the planner has the option to pay a penalty instead of connecting chosen clients.</p
Improved Approximation Algorithm for k-Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter
No full text
An Improved Ant-Colony Clustering Algorithm Based on the Innovational Distance Calculation Formula
No full textFault Diagnosis Algorithm Based on Power Outage Data in Power Grid
No full textINTRODUCTION: With the rapid development of the power industry, the power system has become more and more complex and prone to failures, which seriously impacts power supply and safety.
OBJECTIVES: Development of efficient and accurate fault diagnosis algorithms for power systems.
METHODS:Proposes a fault diagnosis algorithm based on outage data to construct an outage fault prediction model using accurate data. First, the outage data are collected, pre-processed, feature extracted and reduced to obtain a more efficient data set. Then, an optimized fault diagnosis algorithm is designed based on logit, support vector machine (SVM) and decision tree (DT) to improve the accuracy and efficiency of fault diagnosis.
RESULTS: The method is applied to the natural power system, and the results show that the optimization algorithm outperforms the traditional methods. Specifically, the accuracy of the optimization algorithm can reach 100%, while the accuracy of the traditional logit algorithm and SVM algorithm is only 84% and 93%, which is a significant improvement in the model prediction performance.
CONCLUSION: The author can significantly optimize the performance of its model and construct an outage data mining algorithm with a good predictive ability to achieve grid fault research and judgment, which has a specific application value in the practical field
Systematic feature selection improves accuracy of methylation-based forensic age estimation in Han Chinese males
No full textCase report: Severe pneumonia and pneumomediastinum in a previously robust adolescent caused by Omicron BA.5.2
No full textThe manifestation of severe pneumonia is only occasional, and pneumomediastinum is a condition that occurs rarely in Coronavirus disease 2019 (COVID-19) patients, especially in those patients who are infected with the Omicron variant. In addition, whether severe pneumonia or pneumomediastinum often occurs in patients in older age, in poor physical condition, or with underlying diseases remains to be ascertained. To date, severe pneumonia and pneumomediastinum due to Omicron infection had not been reported in a young patient with an excellent physical condition. In this study, we report such a case with the aforementioned manifestations in a robust adolescent infected with Omicron BA.5.2
Spatiotemporal Variations in Agricultural Flooding in Middle and Lower Reaches of Yangtze River from 1970 to 2018
No full textAgricultural floods in the middle and lower reaches of the Yangtze River, known as the “land of fish and rice” in China, have increased both in areal coverage and frequency over the past 50 years, presenting a grave challenge to sustainable development and food security in the region. Studying the spatiotemporal variation characteristics of agricultural floods in this region is thus important for providing a scientific basis for regional flood control and disaster mitigation. We used variation trend analyses, Mann–Kendall tests, wavelet analyses, and center of gravity modeling to study spatiotemporal changes in agricultural floods in the study area, based on agricultural flood indicators. Changes in agricultural flood frequency showed an overall increasing trend. The frequency of floods changed abruptly in 1990, with the average frequency of floods per station increasing by 0.2086/year from 1991 through 2018, characterized by multiple time-scale changes. The time scale of 17 years had three low–high cycles, that of eight years had six, and that of four years had 13. Agricultural floods in the study area were concentrated in the southern Yangtze River and mainly occurred in northeastern Jiangxi Province and the southeastern Zhejiang Province. The area with high agricultural flood indices increased. Agricultural floods were closely related to the Yangtze River and the direction of the gravity center of agricultural floods was similar to that of the river. Affected by precipitation intensity and frequency, the gravity center fluctuated greatly and generally alternated from southwest to northeast
