subject:(Cutset)

Queens University

1. Wu, Szu Kuan Steven. Lossless Coding of Markov Random Fields with Complex Cliques .

Degree: Mathematics and Statistics, 2013, Queens University

URL: http://hdl.handle.net/1974/8166

► The topic of Markov Random Fields (MRFs) has been well studied in the past, and has found practical use in various image processing, and machine… (more)

Subjects/Keywords: Markov Random Fields ; Applied Probability ; Belief Propagation ; Reduced Cutset Coding ; Information Theory ; Complex Cliques ; Computer Science

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Wu, S. K. S. (2013). Lossless Coding of Markov Random Fields with Complex Cliques . (Thesis). Queens University. Retrieved from http://hdl.handle.net/1974/8166

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Wu, Szu Kuan Steven. “Lossless Coding of Markov Random Fields with Complex Cliques .” 2013. Thesis, Queens University. Accessed January 16, 2021. http://hdl.handle.net/1974/8166.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Wu, Szu Kuan Steven. “Lossless Coding of Markov Random Fields with Complex Cliques .” 2013. Web. 16 Jan 2021.

Vancouver:

Wu SKS. Lossless Coding of Markov Random Fields with Complex Cliques . [Internet] [Thesis]. Queens University; 2013. [cited 2021 Jan 16]. Available from: http://hdl.handle.net/1974/8166.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Wu SKS. Lossless Coding of Markov Random Fields with Complex Cliques . [Thesis]. Queens University; 2013. Available from: http://hdl.handle.net/1974/8166

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Texas A&M University

2. Luo, Haochen. Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem.

Degree: PhD, Industrial Engineering, 2019, Texas A&M University

URL: http://hdl.handle.net/1969.1/188770

► In this dissertation, we develop new methodologies and algorithms to solve the multi-module (survivable) network design problem. Many real-world decision-making problems can be modeled as… (more)

▼ In this dissertation, we develop new methodologies and algorithms to solve the multi-module (survivable) network design problem. Many real-world decision-making problems can be modeled as network design problems, especially on networks with capacity requirements on arcs or edges. In most cases, network design problems of this type that have been studied involve different types of capacity sizes (modules), and we call them the multi-module capacitated network design (MMND) problem. MMND problems arise in various industrial applications, such as transportation, telecommunication, power grid, data centers, and oil production, among many others. In the first part of the dissertation, we study the polyhedral structure of the MMND problem. We summarize current literature on polyhedral study of MMND, which generates the family of the so-called cutset inequalities based on the traditional mixed integer rounding (MIR). We then introduce a new family of inequalities for MMND based on the so-called n-step MIR, and show that various classes of cutset inequalities in the literature are special cases of these inequalities. We do so by studying a mixed integer set, the cutset polyhedron, which is closely related to MMND. We We also study the strength of this family of inequalities by providing some facet-defining conditions. These inequalities are then tested on MMND instances, and our computational results show that these classes of inequalities are very effective for solving MMND problems. Generalizations of these inequalities for some variants of MMND are also discussed. Network design problems have many generalizations depending on the application. In the second part of the dissertation, we study a highly applicable form of SND, referred to as multi-module SND (MM-SND), in which transmission capacities on edges can be sum of integer multiples of differently sized capacity modules. For the first time, we formulate MM-SND as a mixed integer program (MIP) using preconfigured-cycles (p-cycles) to reroute flow on failed edges. We derive several classes of valid inequalities for this MIP, and show that the valid inequalities previously developed in the literature for single-module SND are special cases of our inequalities. Furthermore, we show that our valid inequalities are facet-defining for MM-SND in many cases. Our computational results, using a heuristic separation algorithm, show that these inequalities are very effective in solving MM-SND. In particular they are more effective than compared to using single-module inequalities alone. Lastly, we generalize the inequalities for MMND for other mixed integer sets relaxed from MMND and the cutset polyhedron. These inequalities also generalize several valid inequalities in the literature. We conclude the dissertation by summarizing the work and pointing out potential directions for future research. Advisors/Committee Members: Kianfar, Kiavash (advisor), Butenko, Sergiy (committee member), Moreno-Centeno, Erick (committee member), Chen, Jianer (committee member).

Subjects/Keywords: mixed-integer programming; network design; cutset inequalities; valid inequalities; n-step MIR

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Luo, H. (2019). Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem. (Doctoral Dissertation). Texas A&M University. Retrieved from http://hdl.handle.net/1969.1/188770

Chicago Manual of Style (16^th Edition):

Luo, Haochen. “Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem.” 2019. Doctoral Dissertation, Texas A&M University. Accessed January 16, 2021. http://hdl.handle.net/1969.1/188770.

MLA Handbook (7^th Edition):

Luo, Haochen. “Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem.” 2019. Web. 16 Jan 2021.

Vancouver:

Luo H. Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem. [Internet] [Doctoral dissertation]. Texas A&M University; 2019. [cited 2021 Jan 16]. Available from: http://hdl.handle.net/1969.1/188770.

Council of Science Editors:

Luo H. Valid Inequalities and Facets for Multi-Module (Survivable) Capacitated Network Design Problem. [Doctoral Dissertation]. Texas A&M University; 2019. Available from: http://hdl.handle.net/1969.1/188770

Universiteit Utrecht

3. Timmer, S.T. Exact Algorithms for Loop Cutset.

Degree: 2012, Universiteit Utrecht

URL: http://dspace.library.uu.nl:8080/handle/1874/253746

► The LOOP CUTSET problem was historically posed by Pearl as a subroutine in Pearl’s algorithm for computing inference in probabilistic networks. The efficiency of the… (more)

Subjects/Keywords: LOOP CUTSET; MAXIMUM INDUCED FOREST; Exact Algorithms; Treewidth; Cut & Count; Branch & Bound; Branch & Reduce; FEEDBACK VERTEX SET

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Timmer, S. T. (2012). Exact Algorithms for Loop Cutset. (Masters Thesis). Universiteit Utrecht. Retrieved from http://dspace.library.uu.nl:8080/handle/1874/253746

Chicago Manual of Style (16^th Edition):

Timmer, S T. “Exact Algorithms for Loop Cutset.” 2012. Masters Thesis, Universiteit Utrecht. Accessed January 16, 2021. http://dspace.library.uu.nl:8080/handle/1874/253746.

MLA Handbook (7^th Edition):

Timmer, S T. “Exact Algorithms for Loop Cutset.” 2012. Web. 16 Jan 2021.

Vancouver:

Timmer ST. Exact Algorithms for Loop Cutset. [Internet] [Masters thesis]. Universiteit Utrecht; 2012. [cited 2021 Jan 16]. Available from: http://dspace.library.uu.nl:8080/handle/1874/253746.

Council of Science Editors:

Timmer ST. Exact Algorithms for Loop Cutset. [Masters Thesis]. Universiteit Utrecht; 2012. Available from: http://dspace.library.uu.nl:8080/handle/1874/253746

4. Reyes, Matthew G. Cutset Based Processing and Compression of Markov Random Fields.

Degree: PhD, Electrical Engineering: Systems, 2011, University of Michigan

URL: http://hdl.handle.net/2027.42/84510

► This thesis presents results related to the compression a Markov random field (MRF) bfX defined on a graph G=(V,E) by first losslessly compressing a cutset… (more)

▼ This thesis presents results related to the compression a Markov random field (MRF) bfX defined on a graph G=(V,E) by first losslessly compressing a cutset of sites U and then either losslessly compressing or estimating the remaining sites conditioned on the cutset. We present analytical solutions to the MAP estimate of a block conditioned on the commonly occurring boundaries with two or fewer runs of black, for both 4 pt. and 8 pt. grid graphs. Using these results we empirically demonstrate that Max-Product Loopy Belief Propagation converges to the correct results. We present a simple adaptive Arithmetic Encoding (AC) based method for losslessly compressing a square grid cutset of a binary image and, applying the Ising reconstruction results, show that the resulting lossy image coder is competitive compared to other methods. We present rigorous development of Local Conditioning for MRFs, algorithm for exact inference in cyclic graphs. We prove that the entropy of family of MRFs is monotone increasing in the associated exponential parameters and that the exponential parameters for the moment-matching reduced MRF induced by U for a subset of nodes are component-wise greater than the original exponential parameters within U. We also show that the divergence between an MRF induced by exponential parameter θ and another induced by θ' is monotone increasing in θ'. Furthermore, we prove that the divergence between the marginal distribution for bfX and reduced MRF follows a Pythagorean decomposition, providing reduced MRF analogue to well-known result in information geometry. We present efficient algorithms for optimal AC based lossless compression of acyclic and EASY cyclic MRFs, and use these for suboptimal lossless compression for HARD cyclic MRFs, called {em Reduced Cutset Coding}. Experiments with RCC on homogeneous Ising models both verify nearly optimal performance and provide estimates of upper and lower bounds to entropy. Advisors/Committee Members: Neuhoff, David L. (committee member), Blass, Andreas R. (committee member), Hero Iii, Alfred O. (committee member), Pappas, Thrasyvoulos N. (committee member), Sadanandarao, Sandeep P. (committee member).

Subjects/Keywords: Markov Random Fields; Source Coding; Belief Propagation; Cutset; Ising Model; Monotonicity; Electrical Engineering; Engineering

…III. Lossy Cutset Coding of Ising Model . . . . . . . . . . . . . . . 40 2.4 2.5 3.1 3.2… …Lossy Cutset Coding . . . . . . . . . . . . . . . . . . . . . . . Analytical Block MAP… …the Grid Cutset and Rate Analysis . . . . . . . . . Proofs… …Out Loop Cutset Nodes . 4.3.3 Complexity of LC . . . . . . . . . . . . . . . . . Example… …Checkerboard Loop Cutset on 4 pt. Grid Graph Proofs…

10 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Reyes, M. G. (2011). Cutset Based Processing and Compression of Markov Random Fields. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/84510

Chicago Manual of Style (16^th Edition):

Reyes, Matthew G. “Cutset Based Processing and Compression of Markov Random Fields.” 2011. Doctoral Dissertation, University of Michigan. Accessed January 16, 2021. http://hdl.handle.net/2027.42/84510.

MLA Handbook (7^th Edition):

Reyes, Matthew G. “Cutset Based Processing and Compression of Markov Random Fields.” 2011. Web. 16 Jan 2021.

Vancouver:

Reyes MG. Cutset Based Processing and Compression of Markov Random Fields. [Internet] [Doctoral dissertation]. University of Michigan; 2011. [cited 2021 Jan 16]. Available from: http://hdl.handle.net/2027.42/84510.

Council of Science Editors:

Reyes MG. Cutset Based Processing and Compression of Markov Random Fields. [Doctoral Dissertation]. University of Michigan; 2011. Available from: http://hdl.handle.net/2027.42/84510

5. Xiong, Xin. Efficient Jacobian Determination by Structure-Revealing Automatic Differentiation.

Degree: 2014, University of Waterloo

URL: http://hdl.handle.net/10012/8197

► This thesis is concerned with the efficient computation of Jacobian matrices of nonlinear vector maps using automatic differentiation (AD). Specifically, we propose the use of… (more)

Subjects/Keywords: Automatic differentiation; Forward mode; Reverse mode; Directed acyclic graph; Computational graph; Directed edge separator; Jacobian matrix; Newton step; Minimum cutset; Ford-Fulkerson algorithm; Sparsity technique; Hidden structure

…is in G − S − T , assign 1 to it as its weight, otherwise assign infinity to it. The cutset… …cutset by algorihtm described in Algorithm 3.2.3. We use the AD-tool, ADMAT [31], to… …see improvements. If cutset method is used, JE defined by equation (2.12) will be…

10 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Xiong, X. (2014). Efficient Jacobian Determination by Structure-Revealing Automatic Differentiation. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/8197

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Xiong, Xin. “Efficient Jacobian Determination by Structure-Revealing Automatic Differentiation.” 2014. Thesis, University of Waterloo. Accessed January 16, 2021. http://hdl.handle.net/10012/8197.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Xiong, Xin. “Efficient Jacobian Determination by Structure-Revealing Automatic Differentiation.” 2014. Web. 16 Jan 2021.

Vancouver:

Xiong X. Efficient Jacobian Determination by Structure-Revealing Automatic Differentiation. [Internet] [Thesis]. University of Waterloo; 2014. [cited 2021 Jan 16]. Available from: http://hdl.handle.net/10012/8197.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Xiong X. Efficient Jacobian Determination by Structure-Revealing Automatic Differentiation. [Thesis]. University of Waterloo; 2014. Available from: http://hdl.handle.net/10012/8197

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Wilfrid Laurier University

6. Gorbonos, Elizabeth. Separability and Vertex Ordering of Graphs.

Degree: 2019, Wilfrid Laurier University

URL: https://scholars.wlu.ca/etd/2148

► Many graph optimization problems, such as finding an optimal coloring, or a largest clique, can be solved by a divide-and-conquer approach. One such well-known technique… (more)

Subjects/Keywords: graph theory; decomposition; clique cutset; simplicial extreme; even-hole; kite; Theory and Algorithms

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Gorbonos, E. (2019). Separability and Vertex Ordering of Graphs. (Thesis). Wilfrid Laurier University. Retrieved from https://scholars.wlu.ca/etd/2148

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Gorbonos, Elizabeth. “Separability and Vertex Ordering of Graphs.” 2019. Thesis, Wilfrid Laurier University. Accessed January 16, 2021. https://scholars.wlu.ca/etd/2148.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Gorbonos, Elizabeth. “Separability and Vertex Ordering of Graphs.” 2019. Web. 16 Jan 2021.

Vancouver:

Gorbonos E. Separability and Vertex Ordering of Graphs. [Internet] [Thesis]. Wilfrid Laurier University; 2019. [cited 2021 Jan 16]. Available from: https://scholars.wlu.ca/etd/2148.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Gorbonos E. Separability and Vertex Ordering of Graphs. [Thesis]. Wilfrid Laurier University; 2019. Available from: https://scholars.wlu.ca/etd/2148

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

		in
And / Or
		in
And / Or
		in
And / Or
		in

Open Access Theses and Dissertations