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.展开更多
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...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 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.展开更多
The steered covariance matrix(STCM) and its inverse matrix should be calculated in each beam for steered minimum variance(STMV) . The inverse matrix needs complex computation and restricts its application in engineeri...The steered covariance matrix(STCM) and its inverse matrix should be calculated in each beam for steered minimum variance(STMV) . The inverse matrix needs complex computation and restricts its application in engineering. Combining the integration character of one-phase regressive filter with the iterative formula of inverse matrix,an STMV iterative algorithm is proposed. The computational cost of the iterative algorithm is reduced approximately to be 2/M times of the original one when there are M sensors,and is more advantaged for the realization of the algorithm in real time. Simulation results show that the STMV iterative algorithm can preserve the characters of STMV on high azimuth resolution and weak target detection while the computational cost reduced sharply. The analysis on sea trial data proves that the proposed algorithm can estimate each target's azimuth even when the source powers differ in large scales or their bearings are very approximate.展开更多
Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different c...Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.展开更多
基金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.
文摘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 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.
文摘The steered covariance matrix(STCM) and its inverse matrix should be calculated in each beam for steered minimum variance(STMV) . The inverse matrix needs complex computation and restricts its application in engineering. Combining the integration character of one-phase regressive filter with the iterative formula of inverse matrix,an STMV iterative algorithm is proposed. The computational cost of the iterative algorithm is reduced approximately to be 2/M times of the original one when there are M sensors,and is more advantaged for the realization of the algorithm in real time. Simulation results show that the STMV iterative algorithm can preserve the characters of STMV on high azimuth resolution and weak target detection while the computational cost reduced sharply. The analysis on sea trial data proves that the proposed algorithm can estimate each target's azimuth even when the source powers differ in large scales or their bearings are very approximate.
文摘Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.
