We consider a team formation problem in multi-dimensional space where the goal is to group a set of n agents into a teams, each of size b, to maximize their total performance. The performance of each team is measured by a score, which is the sum of h highest skill values in each dimension. We wish to maximize the sum of team scores. We prove that the problem is NP-hard if the dimension is d = Omega(log n), even for scoring parameter h=1 and team size b = 4. We then describe an efficient algorithm for solving the problem in two dimensions, as well an algorithm for computing a single optimal team in any constant dimension.

Geometric techniques are frequently utilized to analyze and reason about multi-dimensional data. When confronted with large quantities of such data, simplifying geometric statistics or summaries are often a necessary first step. In this thesis, we make contributions to two such fundamental concepts of computational geometry: Klee's Measure and Convex Hulls. The former is concerned with computing the total volume occupied by a set of overlapping rectangular boxes in d-dimensional space, while the latter is concerned with identifying extreme vertices in a multi-dimensional set of points. Both problems are frequently used to analyze optimal solutions to multi-objective optimization problems: a variant of Klee's problem called the Hypervolume Indicator gives a quantitative measure for the quality of a discrete Pareto Optimal set, while the Convex Hull represents the subset of solutions that are optimal with respect to at least one linear optimization function.

In the first part of the thesis, we investigate several practical and natural variations of Klee's Measure Problem. We develop a specialized algorithm for a specific case of Klee's problem called the “grounded” case, which also solves the Hypervolume Indicator problem faster than any earlier solution for certain dimensions. Next, we extend Klee's problem to an uncertainty setting where the existence of the input boxes are defined probabilistically, and study computing the expectation of the volume. Additionally, we develop efficient algorithms for a discrete version of the problem, where the volume of a box is redefined to be the cardinality of its overlap with a given point set.

The second part of the thesis investigates the convex hull problem on uncertain input. To this extent, we examine two probabilistic uncertainty models for point sets. The first model incorporates uncertainty in the existence of the input points. The second model extends the first one by incorporating locational uncertainty. For both models, we study the problem of computing the probability that a given point is contained in the convex hull of the uncertain points. We also consider the problem of finding the most likely convex hull, i.e., the mode of the convex hull random variable.

In a geometric optimization problem, the goal is to optimize an objective function

subject to a set of constraints induced by a family of geometric objects. When these

constraints render the problem infeasible or cause the objective function value to be unacceptable,

a natural course of action is to remove or relax some of the constraints,

without changing the problem formulation too much. In this dissertation, we study some natural

formulations of two geometric optimization problems

subject to a fixed budget on the number of constraints that can be removed.

For most parts, our focus is on path finding problems in the plane in presence of polygonal obstacles,

where we are allowed to remove a small number of the obstacles. We first consider the case when

obstacles are overlapping such that no "feasible" path between a given source s and destination t exists.

Here, one would like to remove the minimum number of obstacles so that there exists an obstacle-free s--t path.

This problem is more commonly known as minimum constraint removal (MCR), and is known to be NP-hard,

even when obstacles are axis-aligned rectangles. We design approximation algorithms for MCR, which are based

on solving the related problem of computing a minimum color path in a colored graph.

Next, we consider the case when obstacles are disjoint (so a feasible path always exists) but even the shortest such

path is unacceptably long. For this case, we design polynomial-time algorithms to compute a set of at most k obstacles

removing which reduces the original shortest path by maximum amount. An important requirement is that the obstacles must be

convex polygons.

Finally, we consider another geometric optimization problem called maximum exposure.

Here, we are given a set of points P and a set of ranges R covering them,

and we would like to remove a subset of R with at most k ranges so as to `expose' (or uncover)

a maximum number of points. Our work here deals with designing approximation algorithms.

In this dissertation we investigate pursuit evasion problems set in geometric environments. These games model a variety of adversarial situations in which a team of agents, called pursuers, attempts to catch a rogue agent, called the evader. In particular, we consider the following problem: how many pursuers, each with the same maximum speed as the evader, are needed to guarantee a successful capture? Our primary focus is to provide combinatorial bounds on the number of pursuers that are necessary and sufficient to guarantee capture.

The first problem we consider consists of an unpredictable evader that is free to move around a polygonal environment of arbitrary complexity. We assume that the pursuers have complete knowledge of the evader's location at all times, possibly obtained through a network of cameras placed in the environment. We show that regardless of the number of vertices and obstacles in the polygonal environment, three pursuers are always sufficient and sometimes necessary to capture the evader. We then consider several extensions of this problem to more complex environments. In particular, suppose the players move on the surface of a 3-dimensional polyhedral body; how many pursuers are required to capture the evader? We show that 4 pursuers always suffice (upper bound), and that 3 are sometimes necessary (lower bound), for any polyhedral surface with genus zero. Generalizing this bound to surfaces of genus g, we prove the sufficiency of (4g + 4) pursuers. Finally, we show that 4 pursuers also suffice under the "weighted region" constraints, where the movement costs through different regions of the (genus zero) surface have (different) multiplicative weights.

Next we consider a more general problem with a less restrictive sensing model. The pursuers' sensors are visibility based, only providing the location of the evader if it is in direct line of sight. We begin my making only the minimalist assumption that pursuers and the evader have the same maximum speed. When the environment is a simply-connected (hole-free) polygon of n vertices, we show that Θ(n^1/2 ) pursuers are both necessary and sufficient in the worst-case. When the environment is a polygon with holes, we prove a lower bound of Ω(n^2/3 ) and an upper bound of O(n^5/6 ) pursuers, where n includes the vertices of the hole boundaries. However, we show that with realistic constraints on the polygonal environment these bounds can be drastically improved. Namely, if the players' movement speed is small compared to the features of the environment, we give an algorithm with a worst case upper bound of O(log n) pursuers for simply-connected n-gons and O(√h + log n) for polygons with h holes.

The final problem we consider takes a small step toward addressing the fact that location sensing is noisy and imprecise in practice. Suppose a tracking agent wants to follow a moving target in the two-dimensional plane. We investigate what is the tracker's best strategy to follow the target and at what rate does the distance between the tracker and target grow under worst-case localization noise. We adopt a simple but realistic model of relative error in sensing noise: the localization error is proportional to the true distance between the tracker and the target. Under this model we are able to give tight upper and lower bounds for the worst-case tracking performance, both with or without obstacles in the Euclidean plane.

Committee selection is a classical problem in the social sciences where the goal is to choose a fixed number of candidates based on voters’ preferences. The problem naturally models elections in representative democracies or hiring of staff, but also generalizes many other resource allocation problems such as the classical facility location problems where facilities are treated as candidates and users as voters. By explicitly modeling voters’ preferences, the committee selection problem raises a number of interesting and challenging algorithmic problems such as winner determination, fault tolerance, and fairness. In this dissertation, we study four such problems.

For the most part, we consider the committee selection problem in Euclidean d-space where candidates/voters are points and voters’ preferences are implicitly derived using their Euclidean distances to the candidates. Our first problem is to find a winning committee under the well-known Chamberlin-Courant voting rule. The goal here is to choose a committee of k candidates so that the rank of any voter’s most preferred candidate in the committee is minimized. (The problem is also equivalent to the ordinal version of the classical k-center problem.) We show that the problem is NP-hard in any dimension d ≥ 2, and is also hard to approximate. Our main results are three polynomial-time approximation schemes, each of which finds a committee with a good minimax score.

Our second problem deals with fault tolerance in committee selection. We study the following three variants: (1) given a committee and a set of f failing candidates, find their optimal replacement; (2) compute the worst-case replacement score for a given committee under failure of f candidates; and (3) design a committee with the best replacement score under worst-case failures. Our main results are polynomial-time algorithms for three problems in one dimension. We also show that the problems are NP-hard in higher dimensions and give constant-factor approximations for all three problems along with an FPT bicriterion approximation for the optimal committee problem.

In our third problem we consider non-Euclidean elections and study the following two natural questions for a given election: (1) (Winner Verification) Given a subset of candidates (committee) T, is T a winning committee? (2) (Candidate Winner) Given a candidate c, does c belong to a winning committee? We show that both the above problems are hard (coNP-complete and θ_{2}^{P}-complete, respectively) in general, but for the restricted case of single-peaked and single-crossing preferences, they admit efficient algorithms.

Our last problem is the problem of covering a multicolored set of points in R^d using (at most) k disjoint unit-radius balls chosen from a candidate set of unit-radius balls so that each color class is covered fairly in proportion to its size. Specifically, we investigate the complexity of covering the maximum number of points in this setting. In the committee selection terminology, each ball is a candidate and each point is a voter; a voter approves all candidates within a unit-radius ball around it, and our goal is to choose an optimal size k committee under fairness constraints. We show that the problem is NP-hard even in one dimension when the number of colors is not fixed. On the other hand, for a fixed number of colors, we present a polynomial-time exact algorithm in one dimension, and a PTAS in any fixed dimension d ≥ 2.

In low-and middle-income countries (LMICs), women often struggle to access health services through the perinatal period. In addition to supply-side geographical access and financial barriers, in many settings there are also constraints arising from a combination of complex family structures, low female agency, social norms, and a lack of information on the importance of seeking timely care. This combination of factors makes it challenging for policymakers to improve maternal and infant health, as typical policies focus on the supply-side, i.e. reducing cost of care, and improving accessibility. This dissertation presents results from three empirical studies conducted in India on the role of household members in decision-making in accessing perinatal care.

The first paper examines the dynamics between new mothers and their caregivers (spouse, mother, and mother-in-law) in making caregiving decisions for postnatal maternal and infant care. The second paper uses a randomized controlled trial to investigate the impact of targeted health messaging and social learning on antenatal care visits and iron and folic acid tablet consumption among pregnant women co-residing with their mothers-in-law. The third paper uses a cluster randomized trial to evaluate the effectiveness of a mobile messaging service delivering postnatal care information to households, and its impact on maternal and infant health outcomes.

In the first paper, I find that birthing women are more likely to name their caregivers (rather than themselves) as sole decision-makers for infant and maternal care, though agreement between the mother and caregiver on who is the decision-maker is low. I also find that the identity of the primary caregiver significantly affects maternal mental well-being, with lower well-being when the primary caregiver is their mother-in-law. The second paper demonstrates that involving mothers-in-law in a health messaging education intervention increases health-seeking behaviors and improves post-delivery outcomes. In the third paper, I find that a mobile messaging service delivering postnatal care information to the entire household has a positive impact on maternal and infant health outcomes.

Collectively, these papers highlight the importance of considering the influence of family members, particularly the mother-in-law, in designing effective health interventions in LMICs. However, further research is needed to understand the factors that influence behaviors and to develop ways to address and modify strongly held priors and social norms that may hinder health-seeking behaviors. Additionally, this research focuses on the perinatal period, but future avenues of research can explore how this dynamic affects other health behaviors such as family planning and childhood nutrition, as well as resulting morbidity.

Background

Research question

Study design and methods

Results

Interpretation