Closure problem

A Closure problem is a problem in graph theory for finding a set of vertices in a directed graph such that there are no edges from the set to the rest of the graph. More specifically, the minimum closure problem asks for a set of this type with the minimum possible weight in a weighted graph.
Contents
Closure problem
Definition
In a directed graph G = (V, A), a set S of vertices is said to be closed if every successor of every vertex S is also in S. Equivalently, S is closed if it has no outgoing edge.
It may be assumed without loss of generality that G is a directed acyclic graph. For, if it is not acyclic, each of its strongly connected components must either be entirely contained in or entirely disjoint from any closed set. Therefore, the closures of G are in onetoone correspondence with the closures of the condensation of G, a directed acyclic graph that has one vertex for each strongly connected component of G. In weighted closure problems, one may set the weight of any vertex of the condensation to the sum of the weights of the vertices in the corresponding strongly connected component of G.
Minimum closure problem
For a directed graph G = (V, A) with vertex weights w_{i} the minimum closure problem is to find a closed set of total minimum weight. If all the weights are positive or negative, the minimum closure problem is trivial. Indeed, if all weights are positive the empty subgraph is a solution, and if all weights are negative, the whole graph is solution. We may therefore assume that G has both positive and negative weights.
Openpit mining
Picard studied the closure problem on the openpit mining problem, which he modeled as a maximymclosure problem.
Maximum and minimum closure problem
In the maximum closure problem a directed graph G = (V, A) with vertex weights w_{i} is given and we want to find a closed subset of vertices V ' such that is maximum. Picard showed that the maximum closure problem can be solved using a minimum cut procedure. Additionally it is clear that the selection problem is closure problem on a bipartite graph therefore the selection problem is a special case of the closure problem. Maximum and minimum closure problems can be converted to each other by negating the vertex weights. A maximum closure problem can be formulated as follows
Where x_{i} is 1 if the vertex is in the closure and it is 0 otherwise, and the first constraint ensures that if a vertex is in the closure its successor is also in it. Since each row has at most one 1 and one −1 we know that the constraint matrix is totally unimodular and an integer solution is obtained by solving the LP relaxation of the problem.
In order to solve the maximum closure problem we can use the maxflow mincut theorem. Let us construct the st graph for maximum closure problem. The graph has a vertex j for each variable x_{j}. We also add a source s and a sink vertex t. If the weight of the variable w_{j} is positive we include an arc from the source to the vertex j with capacity w_{j}. If the weight is negative we add the arc from j to the sink vertex (t) with capacity −w_{j}. Each inequality x_{j} ≤ x_{i} is associated with an arc (i, j) with capacity ∞. Let V^{+}be the set of vertices with positive weights and V^{−} the set of vertices with negative weights. Figure \ref{fig:cl4} shows the graph constructed for the closure problem. We can find the minimum cut in this graph by solving a maxflow problem from source to the sink . The source set of a minimum cut separating s from t is a maximum closure in the graph. This statement holds because the minimum cut is finite and cannot include any arc from A that has the weight equal to ∞ [5]. Minimizing the value of the finite cut is equivalent to maximizing the sum of weights of the vertices in the source set of the finite cut. Denote (A,B) the collection of arc with tails at A and heads at B. Also where c_{ij}is the capacity of arc (i,j). Let . For a finite cut we have:
In the last expression is a constant. Therefore the closed set of minimum weight is also the sink set of the minimum cut and vice versa—the sink set of a minimum cut (without t), which has to be finite, also minimized the weight of the closure.
History
During the 1970s J.C. Picard was working on the openpit mining problem and during that time worked on generalizing the selection problem to the closure problem. During that time the mining industry was developing optimization methods on their own. Picard's contribution introduced the closure problem to the mining industry.
References
[1] D. S. Hochbaum. Complexity and algorithms for convex network optimization and other nonlinear problems. 4OR , 3:3, 2005, 171  216
[2] D. S. Hochbaum. An efficient algorithm for image segmentation, Markov Random Fields and related problems. Journal of the ACM, Vol 48, No 2, July 2001 pp. 686 – 701.
[3] D. S. Hochbaum. Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today, Management Science, Vol 50:6, pp 709–723, 2004. Link
[4] D. S. Hochbaum. The Pseudo flow algorithm: A new algorithm for the maximum flow problem, Operations Research, Vol 58(4) 9921009, JulyAug (2008).
[5] D. S. Hochbaum, M. Queyranne. Minimizing a convex cost closure set. Siam Journal on Discrete Mathematics, 16:2, 2003, pp 192–207. Extended abstract appeared in Lecture Notes in Computer Science 1879, M. Paterson (ed.), 8th Annual European Symposium on Algorithms  ESA 2000 proceedings pp 256–267.
[6] D. S. Hochbaum, J. George Shanthikumar. Convex separable optimization is not much harder than linear optimization. Journal of the ACM, Volume 37 , Issue 4, Pages: 843  862.
Categories: Mineral economics
 Graph algorithms
Wikimedia Foundation. 2010.
Look at other dictionaries:
closure — closure, social closure Identified in the writings of Max Weber , and more recently resurrected by the British sociologist Frank Parkin, the concept emerged as an alternative to Marxist theories of inequality and of how the latter is generated,… … Dictionary of sociology
Closure (computer science) — In computer science, a closure (also lexical closure, function closure, function value or functional value) is a function together with a referencing environment for the non local variables of that function.[1] A closure allows a function to… … Wikipedia
Closure (philosophy) — For other uses, see Closure (disambiguation). Closure, in epistemology, is the principle that if a subject S knows that p, and S knows that p entails q, then S can thereby come to know that q. Most epistemological theories involve a closure… … Wikipedia
closure — closure [ˈkləuʒə US ˈklouʒər] n 1.) [U and C] when a factory, school, hospital etc has to close permanently ▪ Several military bases are threatened with closure . factory/hospital/school etc closure ▪ the problem of school closures closure of ▪… … Dictionary of contemporary English
Funarg problem — In computer science, the funarg problem refers to the difficulty in implementing first class functions (functions as first class objects) in stack based programming language implementations. The difficulty only arises if the body of a nested… … Wikipedia
Cognitive closure (philosophy) — Problems of inquiry Cognitive closure (philosophy) Cognitive bias (psychology) Empirical limits in science This box: view · talk · … Wikipedia
Causal closure — is a metaphysical theory about the nature of causation in the physical realm with significant ramifications in the study of the mind.DefinitionCausal closure has two main formulations a weak and a strong form. The weak form states: No physical… … Wikipedia
Kuratowski's closurecomplement problem — In the mathematical subject of topology, Kuratowski s closure complement problem refers to the statement that at most 14 distinct sets can be obtained by repeatedly applying the set operations of closure and complement to a given starting subset… … Wikipedia
Transitive closure — In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R .For example, if X is a set of airports and xRy means there is a direct flight from airport x to airport y , then… … Wikipedia
Back closure — A back closure is a fastener (such as a zipper or button(s)) on the rear of a garment, most commonly one made for females. They were a common feature of women s and girls clothes in the past, and were the preferred choice of some women for more… … Wikipedia