Rice University Graduate Electronic Theses and Dissertationshttp://hdl.handle.net/1911/82992019-10-18T03:34:17Z2019-10-18T03:34:17ZMonitoring on Graphs: An Exploration into k-Cores, Zero Forcing, and Power Dominationhttp://hdl.handle.net/1911/1074572019-10-17T13:06:31Z2019-10-16T00:00:00ZMonitoring on Graphs: An Exploration into k-Cores, Zero Forcing, and Power Domination
This thesis will cover various computational models for approximating and solving multiple graph monitoring problems. The first problem of interest is the Minimum k-core problem, which asks for the smallest induced subgraph of minimum degree k. It has been shown that this problem is difficult and thus sophisticated techniques are required to obtain good solutions. The minimum k-core problem is modeled as a binary integer program and relaxed as a linear program. Since the relaxation may yield a non-integral solution, a Branch-and-Cut framework is used to find the integral optimal solution. It is shown that the edge and cycle transversals of the graph give valid inequalities for the convex hull of the k-core polytope - which can be further generalized to a family of l-core transversals. Further, a heuristic for the hitting set of the minimal l-cores is given with its associated valid inequality. Additionally, improved valid inequalities are generated using bounds generated via the girth of the graph. Multiple low order heuristics are explored for finding initial bounds for the branching process utilizing the degree distribution of the graph. Finally, numerical results are given comparing the Branch-and-Bound, Branch-and-Cut, and heuristic techniques.
The next problem that is studied is the Zero Forcing Problem. Zero forcing is a graph coloring process based on the following color change rule: all vertices of a graph G are initially colored either blue or white; in each time-step, a white vertex turns blue if it is the only white neighbor of some blue vertex. A zero forcing set of G is a set of blue vertices such that all vertices eventually become blue after iteratively applying the color change rule. The zero forcing number Z(G) is the cardinality of a minimum zero forcing set. This thesis proposes novel exact algorithms for computing Z(G) based on formulating the zero forcing problem as a two-stage Boolean satisfiability problem with clause generation. Several heuristics are proposed for zero forcing based on iteratively adding blue vertices which color a large part of the remaining white vertices. These heuristics are used to speed up the exact algorithms, and can also be of independent interest in approximating Z(G). Computational results on various types of graphs show that in many cases, the algorithms presented offer a significant improvement on the state-of-the-art algorithms for zero forcing.
Lastly, the Connected Power Domination problem is studied. The study of power domination in graphs arises from the problem of placing a minimum number of measurement devices in an electrical network, while monitoring the entire network. A power dominating set of a graph is a set of vertices from which every vertex in the graph can be observed, following a set of rules for power system monitoring. This thesis studies the problem of finding a minimum power dominating set which is connected; the cardinality of such a set is called the connected power domination number of the graph. It is shown that the connected power domination number of a graph is NP-hard to compute in general, but can be computed in linear time in cactus graphs and block graphs. Various structural results about connected power domination are given. Finally, novel integer programming formulations for power domination, connected power domination, and power propagation time are presented, with their respective computational results showing they perform better than other integer programming models in the literature.
2019-10-16T00:00:00ZA Constructional Reanalysis of Semantic Prosodyhttp://hdl.handle.net/1911/1074382019-10-13T08:42:11Z2019-10-09T00:00:00ZA Constructional Reanalysis of Semantic Prosody
This dissertation is a re-examination of semantic prosody within the framework of construction grammar. The basic idea of semantic prosody is that ostensibly neutral words can have a probabilistic tendency to co-occur with words that express either positive or negative evaluations. Sinclair (1987), for example, notes that the phrasal verb 'set in' tends to occur with nouns like 'decay' or 'despair'; Stubbs (1995) finds that the verb 'cause' often collocates with words like 'problem' or 'damage'.
Even though semantic prosody is an important and much-discussed topic within corpus linguistics, it remains an elusive and contentious subject. There are numerous areas of disagreement in the research literature, e.g. what its function is, at what level it is located, or how it relates to other distributional phenomena such as collocation or semantic preference.
This dissertation proposes a novel account of semantic prosody to solve these issues by examining them through a different quantitative methodology and by contextualizing them within a different theoretical framework. A major limitation of previous studies has been their focus on word-level co-occurrences. Corpus evidence reveals that much of a word's meaning is not invariant but instead differs across constructional contexts. Once this context-dependent nature of meaning is considered, a much clearer image of co-selection between linguistic items emerges.
Evidence from collostructional analysis (Stefanowitsch & Gries 2003), a type of quantitative corpus methodology, demonstrates that constructional patterns are often associated with specific lexical fields, which allow for a detailed description of their semantics. Not only does this reveal that the evaluative meaning of semantic prosody reaches far beyond the simple positive/negative polarity posited in prior research; it also shows that semantic prosody surfaces in language use as an epiphenomenon of more complex evaluative semantics.
With the help of the methodology of quantitative corpus linguistics and the theoretical frameworks of construction grammar and usage-based linguistics, semantic prosody is readily explained as an ordinary part of meaning and does not pose a challenge to linguistic theory.
2019-10-09T00:00:00ZNewton-Based Methods for Smoothed Risk-Averse PDE-Constrained Optimization Problemshttp://hdl.handle.net/1911/1074362019-10-11T08:42:08Z2019-10-09T00:00:00ZNewton-Based Methods for Smoothed Risk-Averse PDE-Constrained Optimization Problems
This thesis introduces a modification for traditional, Newton-based methods to improve the efficiency of solving smoothed, risk-averse PDE-constrained optimization problems arising from optimal control applications. Instead of only maximizing the expected performance of a system, risk-averse formulations penalize deviations of actual performance that are below expected performance. Solving risk-averse optimization problems is notoriously expensive, as the evaluation of the objective function often requires sampling in the tail of a complicated and unknown probability distribution, which depends on the random variables that enter the system through the PDE and through the performance measure. Moreover, many risk measures, like the Conditional-Value-at-Risk, are non-smooth. As a result, many have employed smoothing functions to smooth the objective and allow the use of fast, gradient-based optimization algorithms like Newton's method. However, for iterates that are far from the optimal solution, the resulting Hessian of the smoothed problem is rank-deficient, which hinders the performance of standard algorithms and results in unnecessary PDE solves. A modification for standard Newton-based algorithms, which eliminates the problem arising from the rank-deficient Hessian, is presented. This algorithm is also tailored to reduce the number of linear PDE solves arising from adjoint and Hessian-vector computations when solving sample-based, PDE-constrained optimization problems.
2019-10-09T00:00:00ZLeonard Bernstein's Symphony No. 2: Americanism, Tradition and Modernism in its Relationship to W.H. Auden's The Age of Anxietyhttp://hdl.handle.net/1911/1074352019-10-08T08:39:39Z2019-10-04T00:00:00ZLeonard Bernstein's Symphony No. 2: Americanism, Tradition and Modernism in its Relationship to W.H. Auden's The Age of Anxiety
Bernstein's Second Symphony, titled The Age of Anxiety after W.H. Auden's epic poem of the same name, is an essentially American work. In this document, I explore the relationship between Bernstein's symphony and Auden's poem in light of elements present in both works that are American in nature, with special attention to both artists' inclusion of multi-national and multi-cultural components in each work as a representation of America. I also examine the manner in which both Bernstein and Auden, as modern artists, position their works in relation to modernism movements in both poetry and music and how both artists chose to maintain a fundamentally traditional foundation in their language and aesthetic, while pursuing a progressive path for their art. Finally, I explore the ways in which Auden's poem appealed to Bernstein on a personal level, especially its overall narrative of the search for faith.
2019-10-04T00:00:00Z