Approximation Algorithms for Network Design and Orienteering

This thesis presents approximation algorithms for some NP-Hard combinatorial optimization problems on graphs and networks; in particular, we study problems related to Network Design. Under the widely-believed complexity-theoretic assumption that P is not equal to NP, there are no efficient (i.e., polynomial-time) algorithms that solve these problems exactly. Hence, if one desires efficient algorithms for such problems, it is necessary to consider approximate solutions: An approximation algorithm for an NP-Hard problem is a polynomial time algorithm which, for any instance of the problem, finds a solution whose value is guaranteed to be within a multiplicative factor of the value of an optimal solution to that instance. We attempt to design algorithms for which this factor, referred to as the approximation ratio of the algorithm, is as small as possible. The field of Network Design comprises a large class of problems that deal with constructing networks of low cost and/or high capacity, routing data through existing networks, and many related issues. In this thesis, we focus chiefly on designing fault-tolerant networks. Two vertices u,v in a network are said to be k-edge-connected if deleting any set of k − 1 edges leaves u and v connected; similarly, they are k-vertex connected if deleting any set of k − 1 other vertices or edges leaves u and v connected. We focus on building networks that are highly connected, meaning that even if a small number of edges and nodes fail, the remaining nodes will still be able to communicate. A brief description of some of our results is given below. We study the problem of building 2-vertex-connected networks that are large and have low cost. Given an n-node graph with costs on its edges and any integer k, we give an O(log n log k) approximation for the problem of finding a minimum-cost 2-vertex-connected subgraph containing at least k nodes. We also give an algorithm of similar approximation ratio for maximizing the number of nodes in a 2-vertex-connected subgraph subject to a budget constraint on the total cost of its edges. Our algorithms are based on a pruning process that, given a 2-vertex-connected graph, finds a 2-vertex-connected subgraph of any desired size and of density comparable to the input graph, where the density of a graph is the ratio of its cost to the number of vertices it contains. This pruning algorithm is simple and efficient, and is likely to find additional applications. Recent breakthroughs on vertex-connectivity have made use of algorithms for element-connectivity problems. We develop an algorithm that, given a graph with some vertices marked as terminals, significantly simplifies the graph while preserving the pairwise element-connectivity of all terminals; in fact, the resulting graph is bipartite. We believe that our simplification/reduction algorithm will be a useful tool in many settings. We illustrate its applicability by giving algorithms to find many trees that each span a given terminal set, while being disjoint on edges and non-terminal vertices; such problems have applications in VLSI design and other areas. We also use this reduction algorithm to analyze simple algorithms for single-sink network design problems with high vertex-connectivity requirements; we give an O(k log n)-approximation for the problem of k-connecting a given set of terminals to a common sink. We study similar problems in which different types of links, of varying capacities and costs, can be used to connect nodes; assuming there are economies of scale, we give algorithms to construct low-cost networks with sufficient capacity or bandwidth to simultaneously support flow from each terminal to the common sink along many vertex-disjoint paths. We further investigate capacitated network design, where edges may have arbitrary costs and capacities. Given a connectivity requirement R_uv for each pair of vertices u,v, the goal is to find a low-cost network which, for each uv, can support a flow of R_uv units of traffic between u and v. We study several special cases of this problem, giving both algorithmic and hardness results. In addition to Network Design, we consider certain Traveling Salesperson-like problems, where the goal is to find short walks that visit many distinct vertices. We give a (2 + epsilon)-approximation for Orienteering in undirected graphs, achieving the best known approximation ratio, and the first approximation algorithm for Orienteering in directed graphs. We also give improved algorithms for Orienteering with time windows, in which vertices must be visited between specified release times and deadlines, and other related problems. These problems are motivated by applications in the fields of vehicle routing, delivery and transportation of goods, and robot path planning.

Effects of incomplete combustion on atmospheric chemistry: Black carbon climate forcing and global carbon monoxide emissions

This thesis is actually the composition of two separate studies aimed at further understanding the role of incomplete combustion products on atmospheric chemistry. The first explores the sensitivity of black carbon (BC) forcing to aerosol vertical location since BC has an increased forcing per unit mass when it is located above reflective clouds. We used a column radiative transfer model to produce globally-averaged values of normalized direct radiative forcing (NDRF) for BC over and under different types of clouds. We developed a simple column-weighting scheme based on the mass fractions of BC that are over and under clouds in measured vertical profiles. The resulting NDRF is in good agreement with global 3-D model estimates, supporting the column-weighted model as a tool for exploring uncertainties due to diversity in vertical distribution. BC above low clouds accounts for about 20% of the global burden but 50% of the forcing. We estimate maximum-minimum spread in NDRF due to modeled profiles as about 40% and uncertainty as about 25%. Models overestimate BC in the upper troposphere compared with measurements; modeled NDRF might need to be reduced by about 15%. Redistributing BC within the lowest 4 km of the atmosphere affects modeled NDRF by only about 5% and cannot account for very high forcing estimates. The second study estimated global year 2000 carbon monoxide (CO) emissions using a traditional bottom-up inventory. We applied literature-derived emission factors to a variety of fuel and technology combinations. Combining these with regional fuel use and production data we produced CO emissions estimates that were separable by sector, fuel type, technology, and region. We estimated year 2000 stationary source emissions of 685.9 Tg/yr and 885 Tg/yr if we included adopted mobile sources from EDGAR v3.2FT2000. Open/biomass burning contributed most significantly to global CO burden, while the residential sector, primarily in Asia and Africa, were the largest contributors with respect to contained combustion sources. Industry production in Asia, including brick, cement, iron and steel-making, also contributed significantly to CO emissions. Our estimates of biofuel emissions are lower than most previously published bottom-up estimates while our other fuel emissions are generally in good agreement. Our values are also universally lower than recently estimated CO emissions from models using top-down methods.

Synthesis and structural stability of metal-organic frameworks

Metal-organic frameworks (MOFs) have attracted significant attention during the past decade due to their high porosity, tunable structures, and controllable surface functionalities. Therefore many applications have been proposed for MOFs. All of them however are still in their infancy stage and have not yet been brought into the market place. In this thesis, the background of the MOF area is first briefly introduced. The main components and the motifs of designing MOFs are summarized, followed by their synthesis and postsynthetic modification methods. Several promising application areas of MOFs including gas storage and separation, catalysis and sensing are reviewed. The current status of commercialization of MOFs as new chemical products is also summarized. Examples of the design and synthesis of two new MOF structures Eu(4,4′,4′′,4′′′-(porphine-5,10,15,20-tetrayl)tetrakis(benzoic acid))·2H2O∙xDMF and Zn4O(azobenzene-4,4’-dicarboxylic acid)3∙xNMP are described. The first one contains free-base porphyrin centers and the second one has azobenzene components. Although the structures were synthesized as designed, unfortunately they did not possess the expected properties. The research idea to use MOFs as template materials to synthesize porous polymers is introduced. Several methods are discussed to grow PMMA into IRMOF-1 (Zn4O(benzene-1,4-dicarboxylate)3, IR stands for isoreticular) structure. High concentration of the monomers resulted in PMMA shell after MOF digestion while with low concentration of monomers no PMMA was left after digestion due to the small iii molecular weight. During the study of this chapter, Kitagawa and co-workers published several papers on the same topic, so this part of the research was terminated thereafter. Many MOFs are reported to be unstable in air due to the water molecules in air which greatly limited their applications. By incorporating a number of water repelling functional groups such as trifluoromethoxy group and methyl groups in the frameworks, the water stability of MOFs are shown to be significantly enhanced. Several MOFs inculding Banasorb-22 (Zn4O(2-trifluoromethoxybenzene-1,4-dicarboxylate)3), Banasorb-24 (Zn4O(2, 5-dimethylbenzene-1,4-dicarboxylate)3) and Banasorb-30 (Zn4O(2-methylbenzene-1,4-dicarboxylate)3) were synthesized and proved to have isostructures with IRMOF-1. Banasorb-22 was stable in boiling water steam for one week and Banasorb-30’s shelf life was over 10 months under ambient condition. For comparison, IRMOF-1’s structure collapses in air after a few hours to several days. Although MOF is a very popular research area nowadays, only a few studies have been reported on the mechanical properties of MOFs. Many of MOF’s applications involve high pressure conditions, so it is important to understand the behavior of MOFs under elivated pressures. The mechanical properties of IRMOF-1 and a new MOF structure Eu2(C12N2O4H6)3(DEF)0.87(H2O)2.13 were studied using diamond anvil cells at Advanced Photon Source. IRMOF-1 experienced an irriversible phase transtion to a nonporous phase followed by amorphization under high pressure. Eu2(C12N2O4H6)3(DEF)0.87(H2O)2.13 showed reversible compression under pressure up to 9.08GPa.

Coordinated pricing and inventory management

This dissertation mainly focuses on coordinated pricing and inventory management problems, where the related background is provided in Chapter 1. Several periodic-review models are then discussed in Chapters 2,3,4 and 5, respectively. Chapter 2 analyzes a deterministic single-product model, where a price adjustment cost incurs if the current selling price is changed from the previous period. We develop exact algorithms for the problem under different conditions and find out that computation complexity varies significantly associated with the cost structure. %Moreover, our numerical study indicates that dynamic pricing strategies may outperform static pricing strategies even when price adjustment cost accounts for a significant portion of the total profit. Chapter 3 develops a single-product model in which demand of a period depends not only on the current selling price but also on past prices through the so-called reference price. Strongly polynomial time algorithms are designed for the case without no fixed ordering cost, and a heuristic is proposed for the general case together with an error bound estimation. Moreover, our illustrates through numerical studies that incorporating reference price effect into coordinated pricing and inventory models can have a significant impact on firms' profits. Chapter 4 discusses the stochastic version of the model in Chapter 3 when customers are loss averse. It extends the associated results developed in literature and proves that the reference price dependent base-stock policy is proved to be optimal under a certain conditions. Instead of dealing with specific problems, Chapter 5 establishes the preservation of supermodularity in a class of optimization problems. This property and its extensions include several existing results in the literature as special cases, and provide powerful tools as we illustrate their applications to several operations problems: the stochastic two-product model with cross-price effects, the two-stage inventory control model, and the self-financing model.