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.

Market work and household production in Brazil

This thesis is composed of three papers in which the research questions are related to the double burden that accrues to Brazilian women. The first and second papers address this issue by looking at expenditure decisions about home production. The first paper examines whether the expenditure decisions about production goods, such as white appliances, relative to entertainment goods, such as TVs, are the outcome of a bargaining process between husbands and wives. The second paper looks at the demand for maid services and for production durable goods, examining the extent to which other household members substitute for maid services and durable goods in home production. The third paper addresses the effects of Brazilian women's double burden on their labor market participation by examining whether the occupational choice of Brazilian women is affected by their gender roles and whether entry into other occupations that are not identified as female occupations has become easier since the introduction of anti-discrimination laws in the labor market. The first paper combines two Brazilian data sets: a Brazilian household expenditure survey, Pesquisa de Orçamento Familiares (POF), and a Brazilian household survey, Pesquisa Nacional Por Amostra de Domicílios (PNAD). The results of the first paper indicate that the decision about durable goods ownership is the outcome of a bargaining process between husband and wife. The test on the coefficients of the marriage market variable and the indicators of households in which only the wife and households in which only the husband makes expenditure decisions corroborate the expectations about wives' preferences for production goods. The same data sets as the first paper are used in the second paper. The finding of the second paper indicates that if the marriage market is favorable to women, that is if the ratio of women to men goes from 1.07 to 0.96, the increment in the household probability of owning at least one maid's substitute durable goods is equivalent to 24% the impact of moving a household up one income quintile. Moreover, the results indicate that daughters' time substitutes for wives' time and maid services in home production. Parents may want daughters trained in home production to be able to perform their future role as wives. However, this training comes at a cost to daughters' investment in formal education, narrowing their future career options. The data used in the third paper come from a Brazilian household survey, Pesquisa Nacional Por Amostra de Domicílios (PNAD). Gender roles are responsible for women to choose female-dominated occupations, married women are 1.14 times more likely to work in female-dominated occupations and having a child six years and older increases on average by 12% the probability that women work in female-dominated occupations instead of genderintegrated occupations in 2001. However, it becomes easier for all types of women to enter into male-dominated and gender-integrated occupations in 2001 compared to 1981.