In this paper, we describe the facial structure of the steiner problem in a directed graph by formulating it as a set covering problem. We first characterize trivial facets and derive a necessary condition for nontrivial facets. We also introduce a class of valid inequalities with 0-1 coefficients and show when such inequalities define facets.

The distance d(u,v) from vertex u to vertex v in a digraph G is the length of the shortest directed path from u to v. The eccentricity e(v) of vertex v is the maximum distance of v to any other vertex of G. A vertex u is an eccentric vertex of vertex v if the distance from v to u is equal to the eccentricity of v. The eccentric digraph ED(G) of a digraph G is the digraph that has the same vertex set as G and the arc set defined by: there is an arc from u to v iff v is an eccentric vertex of u. The idea of the eccentric digraph of a graph was introduced by Buckley (Congr. Numer. 149 (2001) 65) and the idea of the eccentric digraph of a digraph by Boland and Miller (Proceedings of AWOCA'01, July 2001, p. 66). In this paper, we examine eccentric digraphs of digraphs for various families of digraphs and we consider the behaviour of an iterated sequence of eccentric digraphs of a digraph. The paper concludes with several open problems.

We study a directed network design problem called the $k$-$(S,T)$-connectivity problem; we design and analyze approximation algorithms and give hardness results. For each positive integer $k$, the minimum cost $k$-vertex connected spanning subgraph problem is a special case of the $k$-$(S,T)$-connectivity problem. We defer precise statements of the problem and of our results to the introduction. For $k=1$, we call the problem the $(S,T)$-connectivity problem. We study three variants of the problem: the standard $(S,T)$-connectivity problem, the relaxed $(S,T)$-connectivity problem, and the unrestricted $(S,T)$-connectivity problem. We give hardness results for these three variants. We design a $2$-approximation algorithm for the standard $(S,T)$-connectivity problem. We design tight approximation algorithms for the relaxed $(S,T)$-connectivity problem and one of its special cases. For any $k$, we give an $O(\log k\log n)$-approximation algorithm, where $n$ denotes the number of vertices. The approximation guarantee almost matches the best approximation guarantee known for the minimum cost $k$-vertex connected spanning subgraph problem which is $O(\log k\log\frac{n}{n-k})$ due to Nutov in 2009.

Models of strategic behavior are usually too complex to conduct large scale analyses, and frequently rely on accurate descriptions of the strategic environment, or unrealistic assumptions which render empirical studies very sensitive to misspecification. This dissertation relates game-theoretic frameworks to models of causality inference and thus provides a reliable method to identify price leadership. Therefore, causal models can be used to study large sets of data without imposing strategic behavior a priori. A case study is provided by analyzing the supply chain relationship among Dominick's Finer Foods and its suppliers. Although our data required aggregation, this empirical analysis successfully determined causal patterns for 60 percent of our sample. Of these price leaderships, 70 percent elicit Manufacturer Stackelberg relationships which tend to be associated with manufacturers that hold big market shares, 25 percent elicit Retailer Stackelbergs which seem to be associated with the biggest retailer margin profits, and only 5 percent elicit a monopolistic retailer with vertical coordination. These results agree with observations made by other authors and the market structure of the 1990's. Moreover, the strategic relationship among the suppliers is also studied. Interestingly, the dominant firms tend to isolate themselves from the price leadership, whereas the second largest firms seem to become price leaders. Our studies agree with the market literature as well. In particular, we find price leadership in a firm which was identified as a low cost leader. Finally, we discovered that the private label does not lead any firm's price unless this firm is the provider of a generic brand.

We study a directed network design problem called the $k$-$(S,T)$-connectivity problem; we design and analyze approximation algorithms and give hardness results. For each positive integer $k$, the minimum cost $k$-vertex connected spanning subgraph problem is a special case of the $k$-$(S,T)$-connectivity problem. We defer precise statements of the problem and of our results to the introduction. For $k=1$, we call the problem the $(S,T)$-connectivity problem. We study three variants of the problem: the standard $(S,T)$-connectivity problem, the relaxed $(S,T)$-connectivity problem, and the unrestricted $(S,T)$-connectivity problem. We give hardness results for these three variants. We design a $2$-approximation algorithm for the standard $(S,T)$-connectivity problem. We design tight approximation algorithms for the relaxed $(S,T)$-connectivity problem and one of its special cases. For any $k$, we give an $O(\log k\log n)$-approximation algorithm, where $n$ denotes the number of vertices. The approximation guarantee almost matches the best approximation guarantee known for the minimum cost $k$-vertex connected spanning subgraph problem which is $O(\log k\log\frac{n}{n-k})$ due to Nutov in 2009.

Edmonds and Giles conjectured that the maximum number of directed joins in a packing is equal to the minimum weight of a directed cut, for any weighted directed graph. This is a generalization of Woodall's Conjecture (which is still open). Schrijver found the first known counterexample to the Edmonds-Giles Conjecture, while Cornuejols and Guenin found the next two. In this thesis we introduce new counterexamples, and prove that all minimal counterexamples of a certain type have now been found.

This paper deals with generalization fo Gershgorin's theorem. This theorem is investigated and generalized in terms of contour integrals, directed graphs, convex analysis, and clock matrices. These results are shown to apply to some specified matrices such as stable and stochastic matrices and some examples will show the relationship of eigenvalue inclusion regions among them.

Edmonds and Giles conjectured that the maximum number of directed joins in a packing is equal to the minimum weight of a directed cut, for any weighted directed graph. This is a generalization of Woodall's Conjecture (which is still open). Schrijver found the first known counterexample to the Edmonds-Giles Conjecture, while Cornuejols and Guenin found the next two. In this thesis we introduce new counterexamples, and prove that all minimal counterexamples of a certain type have now been found.

No / This paper studies the selective maintenance problem for multi-state systems with structural dependence. Each component can be in one of multiple working levels and several maintenance actions are possible to a component in a maintenance break. The components structurally form multiple hierarchical levels and dependence groups. A directed graph is used to represent the precedence relations of components in the system. A selective maintenance optimization model is developed to maximize the system reliability in the next mission under time and cost constraints. A backward search algorithm is used to determine the assembly sequence for a selective maintenance scenario. The maintenance model helps maintenance managers in determining the best combination of maintenance activities to maximize the probability of successfully completing the next mission. Examples showing the use of the proposed method are presented.

Does monetary policy affect the real economy? If so, what is the transmission mechanism or channel through which these effects occur? These two questions are among the most important and controversial in macroeconomics. This dissertation presents some new empirical evidence that addresses each question for the U.S. and Chinese economies. Literature on monetary transmission suggests that the monetary policy can take effect on the real economy through several ways. The most noteworthy one is credit channels, including the bank lending channel and the interest channel. First, I use a new method to test for structural breaks in the U.S. monetary policy history and present some new empirical evidence to support an operative bank lending channel in the transmission mechanism of monetary policy. Results show that an operative bank lending channel existed in 1955 to 1968, and its impact on the economy has become much smaller since 1981, but it still has a significant buffering effect on output by attenuating the effect of the interest channel. Second, I adopt the recently developed time series technique to explore the puzzling negative correlation between output and stock returns in China currently, and posit that it is due to a negative link between monetary policy and stock returns when monetary policy increases output. The monetary policy has not been transmitted well in the public sector which is the principal part of Chinese stock market, and increased investment capital from monetary expansion goes to real estate sector instead of the stock market. Last, I demonstrate how monetary policy has been transmitted into the public and private sectors of China through the credit channel. The fundamental identification problem inherent in using aggregated data that leads to failure in isolating demand shock from supply shock is explicitly solved by introducing control factors. I find that the monetary policy has great impact on private sector rather than public sector through credit channel in China. These findings have important practical implications for U.S. and China’s economic development by improving the efficiency of the monetary policy because a comprehensive understanding of monetary transmission will lead to better policy design.