Submodularity is a key property in discrete optimization. Submodularity has been widely used for analyzing the greedy algorithm to give performance bounds and providing insight into the construction of valid inequalit...
详细信息
Optical networks are widely used today and in case of any natural disaster, they ensure connectivity. Disaster management schemes proposed in past have many problems associated with them; cost of recovery of fiber bei...
详细信息
ISBN:
(纸本)9781728139890
Optical networks are widely used today and in case of any natural disaster, they ensure connectivity. Disaster management schemes proposed in past have many problems associated with them; cost of recovery of fiber being the major one. A small interruption in the optical network results in the loss of large number of data packets during the recovery processes and sometimes the recovery process takes a long time. To address these problems, the low risk failure optical network can be designed by considering the seismic hazard map of India. In this paper, we propose a restoration model to cater the sudden failure in the optical network. New links are added to the network. We have tried to increase the capacity of the safer links and their subsequent physical routes under minimum cost with the aim to reduce the possibilities of failure in the network. The mathematical model for integer linear programming (ILP) for risk aware provisioning scheme has been proposed, the proactive and reactive approach has also been discussed. The proposed scheme reduces the possibility of failure in communication network caused by the disaster.
The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of...
详细信息
In the design of disassembly lines, the equipment requirements is a common index to measure the cost-efficiency of a processing alternative, but it is seldom considered in the literature. This paper investigates the i...
详细信息
In the design of disassembly lines, the equipment requirements is a common index to measure the cost-efficiency of a processing alternative, but it is seldom considered in the literature. This paper investigates the integrated decision of disassembly line balancing and equipment configuration, i.e., the disassembly line design problem. A linear mixed integer programming (MIP) formulation is developed, and a dynamic programming approach is proposed to solve the problem.
Many set selection and ranking algorithms have recently been enhanced with diversity constraints that aim to explicitly increase representation of historically disadvantaged populations, or to improve the overall repr...
详细信息
We present a technique to infer lower bounds on the worst-case runtime complexity of integer programs, where in contrast to earlier work, our approach is not restricted to tail-recursion. Our technique constructs symb...
详细信息
Automatically generating descriptive captions for images is a well-researched area in computer vision. However, existing evaluation approaches focus on measuring the similarity between two sentences disregarding fine-...
详细信息
In temporal ordered clustering, given a single snapshot of a dynamic network, we aim at partitioning its nodes into K ordered clusters C1 ă ¨ ¨ ¨ ă CK such that for i ă j nodes in cluster Ci arrive to t...
详细信息
The p-center problem consists in selecting p centers among M to cover N clients, such that the maximal distance between a client and its closest selected center is minimized. For this problem we propose two new and co...
详细信息
ISBN:
(数字)9783319961514
ISBN:
(纸本)9783319961514;9783319961507
The p-center problem consists in selecting p centers among M to cover N clients, such that the maximal distance between a client and its closest selected center is minimized. For this problem we propose two new and compact integer formulations. Our first formulation is an improvement of a previous formulation. It significantly decreases the number of constraints while preserving the optimal value of the linear relaxation. Our second formulation contains less variables and constraints but it has a weaker linear relaxation bound. We besides introduce an algorithm which enables us to compute strong bounds and significantly reduce the size of our formulations. Finally, the efficiency of the algorithm and the proposed formulations are compared in terms of quality of the linear relaxation and computation time over instances from OR-Library.
Inferring the node arrival sequence from a snapshot of a dynamic network is an important problem, with applications ranging from identifying sources of contagion to flow of capital in financial transaction networks. V...
详细信息
ISBN:
(纸本)9781450356398
Inferring the node arrival sequence from a snapshot of a dynamic network is an important problem, with applications ranging from identifying sources of contagion to flow of capital in financial transaction networks. Variants of this problem have received significant recent research attention, including results on infeasibility of solution for prior formulations. We present a new formulation of the problem that admits probabilistic solutions for broad classes of dynamic network models. Instantiating our framework for a preferential attachment model, we present effectively computable and practically tight bounds on the tradeoff curve between optimal achievable precision and densitylrecall. We also present efficient algorithms for partial recovery of node arrival orders and derive theoretical and empirical performance bounds on the precision and density/recall of our methods in comparison to the best possible. We validate our methods through experiments on both synthetic and real networks to show that their performance is robust to model changes, and that they yield excellent results in practice. We also demonstrate their utility in the context of a novel application in analysis of the human brain connectome to draw new insights into the functional and structural organization and evolution of the human brain.
暂无评论