In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical app...In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical applications in real life.Specifically,given a weighted graph G=(V,E;w,c;v_(1))equipped with a weight function w:E→R^(+)that satisfies the triangle inequality,an interdiction cost function c:E→Z^(+),a fixed depot v_(1)∈V,an integer k∈^Z^(+)and a budget B∈N,we are asked to find a subset S_(K)■E such that c(S_(K))=∑_(e∈S_(k)c_(e))≤B and that the subgraph G\S_(k)is connected,the objective is to minimize the value min_(C_(E)\S_(k))max{w(C_(i))|C_(i)∈C_(E)\S_(K)}among such all aforementioned subsets S_(k),where C_(E)S_(k)is a set of k-tours(of G\S_(k))starting and ending at the depot v_(1),jointly traversing each edge in G\S_(k)at least once,and w(C_(i))=∑e∈C_(i)w(e)for each tour C_(i)∈C_(E)\S_(k).We obtain the following main results:(1)Given an-approximation algorithm to solve the minimization knapsack problem,we design an(α+β)-approximation algorithm to solve the k-CPIBC problem,whereβ=7/2-1/k-[1/k].(2)We present aβ-approximation algorithm to solve the special version of the k-CPIBC problem,where c(e)1 for each edge e in G and is defined in(1).展开更多
This paper considers a novel formulation of the multi-period network interdiction problem. In this model, delivery of the maximum flow as well as the act of interdiction happens over several periods, while the budget ...This paper considers a novel formulation of the multi-period network interdiction problem. In this model, delivery of the maximum flow as well as the act of interdiction happens over several periods, while the budget of resource for interdiction is limit. It is assumed that when an edge is interdicted in a period, the evader considers a rate of risk of detection at consequent periods. Application of the generalized Benders decomposition algorithm considers solving the resulting mixed-integer nonlinear programming problem. Computational experiences denote reasonable consistency with expectations.展开更多
Oil spill occurrence during exploration, production and distribution can cause deleterious impact on the environment. Contamination of local streams/rivers, farmlands, forest resources and biodiversity in oil producin...Oil spill occurrence during exploration, production and distribution can cause deleterious impact on the environment. Contamination of local streams/rivers, farmlands, forest resources and biodiversity in oil producing areas presents strong significant possibility of significant harm to human health. Geo-information technologies present new opportunities for assessing stress environment and ways of determining exposure susceptibility in such areas. The study assesses the geographical distribution of oil-spills cluster and pattern using three geospatial techniques with ground data at 443 oil-spill incident sites from 1985-2008. The places with high (high-volume/ large impact/close proximity to communities) and low incident (low-volume/less impact/far-distance) are related to the quantity of oil-spills identified within those communities considered susceptible to spill impact and possible exposure. While the average nearest neighborhood analysis showed a probability that oil-spill distribution in the area is clustered (ratio < 1 with index value 0.19), the Getis-Ord General G test indicated that the oil-spill with high quantities (volume) discharge are significantly clustered within every 400 m. The Moran’s I index indicted that there is <1% likelihood that the clusters are as a result of random chance. These findings will help to combat the environmental problems and risks of prolong exposure to petroleum hydrocarbons by addressing future incidents or relocating oil facilities/communities and positioning of rapid response strategies.展开更多
Hedge has been proposed as an adaptive scheme, which guides the player’s hand in a multi-armed bandit full information game. Applications of this game exist in network path selection, load distribution, and network i...Hedge has been proposed as an adaptive scheme, which guides the player’s hand in a multi-armed bandit full information game. Applications of this game exist in network path selection, load distribution, and network interdiction. We perform a worst case analysis of the Hedge algorithm by using an adversary, who will consistently select penalties so as to maximize the player’s loss, assuming that the adversary’s penalty budget is limited. We further explore the performance of binary penalties, and we prove that the optimum binary strategy for the adversary is to make greedy decisions.展开更多
Wildlife trafficking is a global phenomenon posing many negative impacts on socio-environmental systems.Scientific exploration of wildlife trafficking trends and the impact of interventions is significantly encumbered...Wildlife trafficking is a global phenomenon posing many negative impacts on socio-environmental systems.Scientific exploration of wildlife trafficking trends and the impact of interventions is significantly encumbered by a suite of data reuse challenges.We describe a novel,open-access data directory on wildlife trafficking and a corresponding visualization tool that can be used to identify data for multiple purposes,such as exploring wildlife trafficking hotspots and convergence points with other crime,discovering key drivers or deterrents of wildlife trafficking,and uncovering structural patterns.Keyword searches,expert elicitation,and peer-reviewed publications were used to search for extant sources used by industry and non-profit organizations,as well as those leveraged to publish academic research articles.The open-access data directory is designed to be a living document and searchable according to multiple measures.The directory can be instrumental in the data-driven analysis of unsustainable illegal wildlife trade,supply chain structure via link prediction models,the value of demand and supply reduction initiatives via multi-item knapsack problems,or trafficking behavior and transportation choices via network interdiction problems.展开更多
基金supported by the National Natural Science Foundation of China(Nos.11861075,12101593)Project for Innovation Team(Cultivation)of Yunnan Province(No.202005AE-160006)+2 种基金Peng-Xiang Pan is also supported by Project of Yunnan Provincial Department of Education Science Research Fund(No.2020Y0040)Jun-Ran Lichen is also supported by Fundamental Research Funds for the Central Universities(No.buctrc202219)Jian-Ping Li is also supported by Project of Yunling Scholars Training of Yunnan Province(No.K264202011820).
文摘In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical applications in real life.Specifically,given a weighted graph G=(V,E;w,c;v_(1))equipped with a weight function w:E→R^(+)that satisfies the triangle inequality,an interdiction cost function c:E→Z^(+),a fixed depot v_(1)∈V,an integer k∈^Z^(+)and a budget B∈N,we are asked to find a subset S_(K)■E such that c(S_(K))=∑_(e∈S_(k)c_(e))≤B and that the subgraph G\S_(k)is connected,the objective is to minimize the value min_(C_(E)\S_(k))max{w(C_(i))|C_(i)∈C_(E)\S_(K)}among such all aforementioned subsets S_(k),where C_(E)S_(k)is a set of k-tours(of G\S_(k))starting and ending at the depot v_(1),jointly traversing each edge in G\S_(k)at least once,and w(C_(i))=∑e∈C_(i)w(e)for each tour C_(i)∈C_(E)\S_(k).We obtain the following main results:(1)Given an-approximation algorithm to solve the minimization knapsack problem,we design an(α+β)-approximation algorithm to solve the k-CPIBC problem,whereβ=7/2-1/k-[1/k].(2)We present aβ-approximation algorithm to solve the special version of the k-CPIBC problem,where c(e)1 for each edge e in G and is defined in(1).
基金Supported by Azarbaijan Shahid Madani University
文摘This paper considers a novel formulation of the multi-period network interdiction problem. In this model, delivery of the maximum flow as well as the act of interdiction happens over several periods, while the budget of resource for interdiction is limit. It is assumed that when an edge is interdicted in a period, the evader considers a rate of risk of detection at consequent periods. Application of the generalized Benders decomposition algorithm considers solving the resulting mixed-integer nonlinear programming problem. Computational experiences denote reasonable consistency with expectations.
文摘Oil spill occurrence during exploration, production and distribution can cause deleterious impact on the environment. Contamination of local streams/rivers, farmlands, forest resources and biodiversity in oil producing areas presents strong significant possibility of significant harm to human health. Geo-information technologies present new opportunities for assessing stress environment and ways of determining exposure susceptibility in such areas. The study assesses the geographical distribution of oil-spills cluster and pattern using three geospatial techniques with ground data at 443 oil-spill incident sites from 1985-2008. The places with high (high-volume/ large impact/close proximity to communities) and low incident (low-volume/less impact/far-distance) are related to the quantity of oil-spills identified within those communities considered susceptible to spill impact and possible exposure. While the average nearest neighborhood analysis showed a probability that oil-spill distribution in the area is clustered (ratio < 1 with index value 0.19), the Getis-Ord General G test indicated that the oil-spill with high quantities (volume) discharge are significantly clustered within every 400 m. The Moran’s I index indicted that there is <1% likelihood that the clusters are as a result of random chance. These findings will help to combat the environmental problems and risks of prolong exposure to petroleum hydrocarbons by addressing future incidents or relocating oil facilities/communities and positioning of rapid response strategies.
文摘Hedge has been proposed as an adaptive scheme, which guides the player’s hand in a multi-armed bandit full information game. Applications of this game exist in network path selection, load distribution, and network interdiction. We perform a worst case analysis of the Hedge algorithm by using an adversary, who will consistently select penalties so as to maximize the player’s loss, assuming that the adversary’s penalty budget is limited. We further explore the performance of binary penalties, and we prove that the optimum binary strategy for the adversary is to make greedy decisions.
基金the National Science Foundation[CMMI-1935451]and National Science Foundation[ISS-2039951]。
文摘Wildlife trafficking is a global phenomenon posing many negative impacts on socio-environmental systems.Scientific exploration of wildlife trafficking trends and the impact of interventions is significantly encumbered by a suite of data reuse challenges.We describe a novel,open-access data directory on wildlife trafficking and a corresponding visualization tool that can be used to identify data for multiple purposes,such as exploring wildlife trafficking hotspots and convergence points with other crime,discovering key drivers or deterrents of wildlife trafficking,and uncovering structural patterns.Keyword searches,expert elicitation,and peer-reviewed publications were used to search for extant sources used by industry and non-profit organizations,as well as those leveraged to publish academic research articles.The open-access data directory is designed to be a living document and searchable according to multiple measures.The directory can be instrumental in the data-driven analysis of unsustainable illegal wildlife trade,supply chain structure via link prediction models,the value of demand and supply reduction initiatives via multi-item knapsack problems,or trafficking behavior and transportation choices via network interdiction problems.
