This paper provides a method of producing a minimum cost spanning tree (MCST) using set operations. It studies the data structure for implementation of set operations and the algorithm to be applied to this structure ...This paper provides a method of producing a minimum cost spanning tree (MCST) using set operations. It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm. This algorithm uses the FDG (formula to divide elements into groups) to sort (the FDG sorts a sequence of n elements in expected tir O(n)) and uses the method of path compression to find and to unite. Therefore. n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).展开更多
The bottleneck analysis of the minimum cost problem for the generalized network (MCPGN) is discussed. The analysis is based on the network simplex algorithm, which gains negative cost graphs by constructing augmented ...The bottleneck analysis of the minimum cost problem for the generalized network (MCPGN) is discussed. The analysis is based on the network simplex algorithm, which gains negative cost graphs by constructing augmented forest structure, then augments flows on the negative cost graphs until the optimal revolution is gained. Bottleneck structure is presented after analyzing the augmented forest structure. The negative cost augmented graphs are constructed with the bottleneck structure. The arcs that block the negative cost augmented graph are the elements of the bottleneck. The bottleneck analysis for the generalized circulation problem, the minimum circulation problem and the circulation problem are discussed respectively as the basal problems, then that for MCPGN is achieved. An example is presented at the end.展开更多
The minimum cost of capacity expansion for time-limited transportation problem on-demand (MCCETLTPD) is to find such a practicable capacity expansion transportation scheme satisfying the time-limited T along with all ...The minimum cost of capacity expansion for time-limited transportation problem on-demand (MCCETLTPD) is to find such a practicable capacity expansion transportation scheme satisfying the time-limited T along with all origins’ supply and all destinations’ demands as well as the expanding cost is minimum. Actually, MCCETLTPD is a balance transportation problem and a variant problem of minimum cost maximum flow problem. In this paper, by creating a mathematical model and constructing a network with lower and upper arc capacities, MCCETLTPD is transformed into searching feasible flow in the constructed network, and consequently, an algorithm MCCETLTPD-A is developed as MCCETLTPD’s solution method basing minimum cost maximum flow algorithm. Computational study validates that the MCCETLTPD-A algorithm is an efficient approach to solving the MCCETLTPD.展开更多
This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building...This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.展开更多
Ontology diagnosis, a well-known approach for handling inconsistencies in a description logic （DL） based ontology, computes a diagnosis of the ontology, i.e., a minimal subset of axioms in the ontology whose removal...Ontology diagnosis, a well-known approach for handling inconsistencies in a description logic （DL） based ontology, computes a diagnosis of the ontology, i.e., a minimal subset of axioms in the ontology whose removal restores consistency. However, ontology diagnosis is computationally hard, especially computing a minimum cost diagnosis （MCD） which is a diagnosis such that the sum of the removal costs attached to its axioms is minimized. This paper addresses this problem by finding data tractable DLs for computing an MCD which allow computing an MCD in time polynomial in the size of the ABox of a given ontology. ABox decomposition is used to find a sufficient and necessary condition to identify data tractable DLs for computing an MCD under the unique name assumption （UNA） among all fragments of that are at least as expressive as without inverse roles. The most expressive, data tractable DL identified is without inverse roles or qualified existential restrictions.展开更多
This paper presents a novel method for multi classifier dynamic combination based on minimum cost criterion.Differentfrom common combination methods,the proposed dynamic combinationselectsthe mostsuitable group ofc...This paper presents a novel method for multi classifier dynamic combination based on minimum cost criterion.Differentfrom common combination methods,the proposed dynamic combinationselectsthe mostsuitable group ofclassifiersaccordingtothe Performance Predication Feature (PPF) extractedfrom theinputsample.PPFs arethefeatures ofsample thathave greatinfluence onthe performance ofclassifiers being studied.The decisionis made based on the criterion thatthe selected group ofclassifiers should minimize the cost caused by recognition errorand recognition time .Systematic methods for making this kind of combination is proposed and a practical example ofapplication is given.Because the adjustment ofcostfunction willresultin differenttrade off between recognitionrate and recognition speed,itis very convenientto satisfy different needs.The application in on line Chinese characterrecognitiontechnologyshowsthatthis kind ofcombination method hasthe merits ofhighflexibility and practicality,anditisindeed able toimprove the system performance .展开更多
Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we c...Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we consider both types of the weighted Hamming distances for measuring the adjustment.In the sum-type case,it is shown that the inverse problem is APX-hard.In the bottleneck-type case,we present a polynomial time algorithm.展开更多
The promulgation of the Rules represents a crucial step toward institutionalization and standardization of the minimum cost of living program, which marks the end of the arbitrariness in the traditional relief behavio...The promulgation of the Rules represents a crucial step toward institutionalization and standardization of the minimum cost of living program, which marks the end of the arbitrariness in the traditional relief behavior. In a country, to what degree the citizens enjoy human rights, it depends on the law. The minimum cost of living system has to be ensured by law in its progress toward institutionalization and standardization. This has been testified by the history of the development of the social security systems, either in Germany, which is regarded as a pioneer in modern social security systems or the United States.展开更多
This study analyzes the sample influx (samples per case file) into forensic science laboratory (FSL) and the corresponding analysis costs and uses arbitrary re-sampling plans to establish the minimum cost function. Th...This study analyzes the sample influx (samples per case file) into forensic science laboratory (FSL) and the corresponding analysis costs and uses arbitrary re-sampling plans to establish the minimum cost function. The demand for forensic analysis increased for all disciplines, especially biology/DNA between 2014 and 2015. While the average distribution of case files was about 42.5%, 40.6% and 17% for the three disciplines, the distribution of samples was rather different being 12%, 82.5% and 5.5% for samples requiring forensic biology, chemistry and toxicology analysis, respectively. Results show that most of the analysis workload was on forensic chemistry analysis. The cost of analysis for case files and the corresponding sample influx varied in the ratio of 35:6:1 and 28:12:1 for forensic chemistry, biology/DNA and toxicology for year 2014 for 2015, respectively. In the two consecutive years, the cost for forensic chemistry analysis was comparatively very high, necessitating re-sampling. The time series of sample influx in all disciplines are strongly stochastic, with higher magnitude for chemistry, biology/DNA and toxicology, in this order. The PDFs of sample influx data are highly skewed to the right, especially forensic toxicology and biology/DNA with peaks at 1 and 3 samples per case file. The arbitrary re-sampling plans were best suited to forensic chemistry case files (where re-sampling conditions apply). The locus of arbitrary number of samples to take from the submitted forensic samples was used to establish the minimum and scientifically acceptable samples by applying minimization function developed in this paper. The cost minimization function was also developed based on the average cost per sample and choice of re-sampling plans depending on the range of sample influx, from which the savings were determined and maximized. Thus, the study gives a forensic scientist a business model and scientific decision making tool on minimum number of samples to analyze focusing on savings on analysis cost.展开更多
文摘This paper provides a method of producing a minimum cost spanning tree (MCST) using set operations. It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm. This algorithm uses the FDG (formula to divide elements into groups) to sort (the FDG sorts a sequence of n elements in expected tir O(n)) and uses the method of path compression to find and to unite. Therefore. n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).
基金Supported by the National Natural Science Foundation of China (No. 60174046).
文摘The bottleneck analysis of the minimum cost problem for the generalized network (MCPGN) is discussed. The analysis is based on the network simplex algorithm, which gains negative cost graphs by constructing augmented forest structure, then augments flows on the negative cost graphs until the optimal revolution is gained. Bottleneck structure is presented after analyzing the augmented forest structure. The negative cost augmented graphs are constructed with the bottleneck structure. The arcs that block the negative cost augmented graph are the elements of the bottleneck. The bottleneck analysis for the generalized circulation problem, the minimum circulation problem and the circulation problem are discussed respectively as the basal problems, then that for MCPGN is achieved. An example is presented at the end.
文摘The minimum cost of capacity expansion for time-limited transportation problem on-demand (MCCETLTPD) is to find such a practicable capacity expansion transportation scheme satisfying the time-limited T along with all origins’ supply and all destinations’ demands as well as the expanding cost is minimum. Actually, MCCETLTPD is a balance transportation problem and a variant problem of minimum cost maximum flow problem. In this paper, by creating a mathematical model and constructing a network with lower and upper arc capacities, MCCETLTPD is transformed into searching feasible flow in the constructed network, and consequently, an algorithm MCCETLTPD-A is developed as MCCETLTPD’s solution method basing minimum cost maximum flow algorithm. Computational study validates that the MCCETLTPD-A algorithm is an efficient approach to solving the MCCETLTPD.
文摘This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.
基金Supported by the National Natural Science Foundation of China(Nos.61005043 and 60970045)
文摘Ontology diagnosis, a well-known approach for handling inconsistencies in a description logic （DL） based ontology, computes a diagnosis of the ontology, i.e., a minimal subset of axioms in the ontology whose removal restores consistency. However, ontology diagnosis is computationally hard, especially computing a minimum cost diagnosis （MCD） which is a diagnosis such that the sum of the removal costs attached to its axioms is minimized. This paper addresses this problem by finding data tractable DLs for computing an MCD which allow computing an MCD in time polynomial in the size of the ABox of a given ontology. ABox decomposition is used to find a sufficient and necessary condition to identify data tractable DLs for computing an MCD under the unique name assumption （UNA） among all fragments of that are at least as expressive as without inverse roles. The most expressive, data tractable DL identified is without inverse roles or qualified existential restrictions.
文摘This paper presents a novel method for multi classifier dynamic combination based on minimum cost criterion.Differentfrom common combination methods,the proposed dynamic combinationselectsthe mostsuitable group ofclassifiersaccordingtothe Performance Predication Feature (PPF) extractedfrom theinputsample.PPFs arethefeatures ofsample thathave greatinfluence onthe performance ofclassifiers being studied.The decisionis made based on the criterion thatthe selected group ofclassifiers should minimize the cost caused by recognition errorand recognition time .Systematic methods for making this kind of combination is proposed and a practical example ofapplication is given.Because the adjustment ofcostfunction willresultin differenttrade off between recognitionrate and recognition speed,itis very convenientto satisfy different needs.The application in on line Chinese characterrecognitiontechnologyshowsthatthis kind ofcombination method hasthe merits ofhighflexibility and practicality,anditisindeed able toimprove the system performance .
文摘Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we consider both types of the weighted Hamming distances for measuring the adjustment.In the sum-type case,it is shown that the inverse problem is APX-hard.In the bottleneck-type case,we present a polynomial time algorithm.
文摘The promulgation of the Rules represents a crucial step toward institutionalization and standardization of the minimum cost of living program, which marks the end of the arbitrariness in the traditional relief behavior. In a country, to what degree the citizens enjoy human rights, it depends on the law. The minimum cost of living system has to be ensured by law in its progress toward institutionalization and standardization. This has been testified by the history of the development of the social security systems, either in Germany, which is regarded as a pioneer in modern social security systems or the United States.
文摘This study analyzes the sample influx (samples per case file) into forensic science laboratory (FSL) and the corresponding analysis costs and uses arbitrary re-sampling plans to establish the minimum cost function. The demand for forensic analysis increased for all disciplines, especially biology/DNA between 2014 and 2015. While the average distribution of case files was about 42.5%, 40.6% and 17% for the three disciplines, the distribution of samples was rather different being 12%, 82.5% and 5.5% for samples requiring forensic biology, chemistry and toxicology analysis, respectively. Results show that most of the analysis workload was on forensic chemistry analysis. The cost of analysis for case files and the corresponding sample influx varied in the ratio of 35:6:1 and 28:12:1 for forensic chemistry, biology/DNA and toxicology for year 2014 for 2015, respectively. In the two consecutive years, the cost for forensic chemistry analysis was comparatively very high, necessitating re-sampling. The time series of sample influx in all disciplines are strongly stochastic, with higher magnitude for chemistry, biology/DNA and toxicology, in this order. The PDFs of sample influx data are highly skewed to the right, especially forensic toxicology and biology/DNA with peaks at 1 and 3 samples per case file. The arbitrary re-sampling plans were best suited to forensic chemistry case files (where re-sampling conditions apply). The locus of arbitrary number of samples to take from the submitted forensic samples was used to establish the minimum and scientifically acceptable samples by applying minimization function developed in this paper. The cost minimization function was also developed based on the average cost per sample and choice of re-sampling plans depending on the range of sample influx, from which the savings were determined and maximized. Thus, the study gives a forensic scientist a business model and scientific decision making tool on minimum number of samples to analyze focusing on savings on analysis cost.
