Search

Abstract: In this thesis, we consider the Traveling Salesman Problem with Neighborhoods (TSPN) on the Euclidean plane, and present a Polynomial-Time Approximation Scheme (PTAS) when the neighborhoods are parallel line segments with lengths between [1, λ] for any constant value λ.In TSPN (which generalizes classic TSP), each client represents a set (or neighborhood) of points in a metric and the goal is to find a minimum cost TSP tour that visits at least one point from each client set. In the Euclidean setting, each neighborhood is a region on the plane.TSPN is significantly more difficult than classic TSP even in the Euclidean setting.A notable case of TSPN is when each neighborhood is a line segment. Although there are PTAS's for when neighborhoods are fat objects (with limited overlap), TSPN over line segments is APX-hard even if all the line segments have unit length. For parallel (unit) line segments, the best approximation factor is 3√2 from 20 years ago.The PTAS we present, settles the approximability of this case of the problem. Our algorithm finds a (1 + ε)-factor approximation for an instance of the problem with n segments with lengths in [1, λ] in time n^O(λ/ε^3).

Abstract: In this thesis, we introduce a new problem called the Minimum Sum Coloring with Bundles. We are given an undirected graph and bundles which bundles are sets of nodes (not necessarily disjoint). The goal is to find a proper coloring of the graph with positive integers to minimize the weighted average/total completion time of all bundles, where the completion time of a bundle is the maximum integer assigned to one of its nodes. This can be viewed as a scheduling problem where nodes are jobs, edges represent constraints on processing jobs simultaneously, and bundles represent sets of jobs a customer wants to finish. We provide the first constant-factor approximation in perfect graphs and some more general graphs. We then extend the problem to a more general model where bundles are disjoint, and we can only color/schedule a limited number of jobs from each bundle at a time. We achieve constant-factor approximations for this model for interval graphs and their generalizations.

Abstract: In this thesis, we design approximation algorithms for a variety of problems in Network Design. The first problem we consider is the Directed Steiner Tree (DST) problem where we want to find a cheapest way of connecting a subset of nodes (terminal nodes) from a root node in a directed network. We give the first logarithmic approximation algorithm for DST on planar graphs. Another restriction of DST we consider is to quasi-bipartite instances on planar graphs. In these instances the underlying graph is planar and no two non-terminal nodes are adjacent. Here we get the first constant factor approximation. We further extend this result to a more general family of graphs called minor-free graphs. Our approach is based on a non-standard primal-dual framework and also bounds the integrality gap of the classical linear programming (LP) relaxation for DST. The third problem we study is a variant of the Traveling Salesman Problem (TSP), one the most famous problem in combinatorial optimization. In TSP, we are given a set of cities, the task is to find a minimum cost tour (closed walk) visiting all the cities. We initiate the study of generalization of TSP, where we are interested in tours that respect some given degree bounds, i.e., a feasible tour must not pass through a location more than a given bound. We further generalize this problem to the setting where we only need to visit a subset of locations in the network. It is easy to see unless P=NP, we cannot hope for an algorithm that does not violate the degree bounds at all. On the other hand, the problems we consider are a generalization of TSP, therefore approximating the cost factor better than the approximation factor for TSP is a very challenging problem. In this thesis, we study the trade-offs between the cost of the tour and the degree violation of the nodes in the tour. We develop LP-based rounding algorithms for these TSP variants which in turn bound the integrality gap of a natural LP relaxations for these problems.

Many of the core challenges in social choice, new and old, stand to benefit from consideration through the computational lens. We demonstrate the particular applicability of approximation algorithms to the tasks of aggregating judgements and preferences for choosing one or more alternatives, and to the construction of representative committees and valuable teams. The first part of this thesis presents contributions to the theory of judgement and preference aggregation in settings where only incomplete information is known. It considers the task of combining expert advice given only incomplete information about experts' competence in order to reach a maximally accurate judgement. For preferences, we consider two settings of choosing alternative(s) given only incomplete information about voters' preferences. In the first we aim to choose a single alternative when only the ranking of voters' valuations of alternatives is known. In the second we aim to select a committee of candidates that all coalitions within the electorate find at least partially acceptable, under the restriction that each voter is only evaluates a few candidates. The second part studies sampling processes which arise in sortition, a direct democratic paradigm in which representative subsets (or panels) of a population are randomly chosen in order to represent the whole. Here the goal of choosing the panel at random is in tension with choosing a maximally representative panel; we present a new framework and approach to making this tradeoff, and further address the challenge of satisfying these aims via a process which is also readily comprehensible to observers. The third part provides algorithmic approaches to group selection problems motivated by hiring, admissions, and team formation. We consider the task of making a collection of simultaneous invitations to candidates who, in contrast to the previous committee selection problems, may decline to be included in the group with some probability. We present approaches to eliciting information from participants and extending sets of invitations in order to realize a group of favorable participants which is close to the target size.

Maximum Constraint satisfaction problems (Max-CSPs) are ubiquitous in computer science and encompass optimization problems such as Max-CUT, Max-DICUT, Max-kSAT, Max-kAND, Max-q-Coloring, Unique Games, etc. Roughly, a Max-CSP has the following structure: there are a set of variables and a set of constraints on the variables, and the goal is to assign the variables in a way so as to maximize the number of constraints that can be satisfied. The polynomial time approximability of Max-CSPs has been the focus of intense study in the literature. More recently, there has been a lot of interest to study combinatorial optimization problems like Max-CSPs in massive data settings like the streaming setting where the input data is scanned sequentially by the algorithm and then processed in a very limited space. Prior to our work, Max-CUT was the only Max-CSP that was extensively studied in this setting. Unfortunately, these studies showed that any non-trivial streaming approximation algorithm for Max-CUT must have enough memory to store the entire input! And the question of obtaining a non-trivial approximation streaming algorithm for some Max-CSP that does not store the whole input was left wide open. The central result in this thesis gives a non-trivial polylogarithmic space streaming approximation algorithm for every Max-CSP along with a sharp dichotomy theorem showing that our algorithm is optimal among subpolynomial space ``sketching'' algorithms---a special class of streaming algorithms used widely in practice, where the algorithm's output is determined by a small sketch it produces of the input stream, and the sketch itself has the property that the sketch of the concatenation of two streams can be computed from the sketches of the two component streams. The first part of this thesis focuses on Max-DICUT which has emerged as central problem in the study of Max-CSPs in the streaming setting. The second part focuses on the dichotomy theorem and some of its consequences for Max-CSPs.

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 this thesis, we study the role of adaptivity in decision-making problems under uncertainty. The first part of the thesis focuses on combinatorial problems, while the second part of the thesis deals with the $K$-armed dueling bandits problem. Combinatorial optimization captures many natural decision-making problems such as matching, load balancing, assortment optimization, network design, and submodular optimization. In many practical settings, we have to solve such combinatorial problems under uncertainty; specifically when we only have partial knowledge about the input. Solutions to such problems are sequential decision processes that make decisions one by one “adaptively” (depending on prior observations). While such adaptive solutions achieve the best objective, the inherently sequential nature makes them undesirable in many applications. Specifically, we ask: how well can solutions with only a few adaptive rounds approximate fully adaptive solutions? (1) We study (and answer) the above question for the stochastic submodular cover and scenario submodular cover problems. These models capture many problems such as sensor placement with unreliable sensors, optimal decision tree, stochastic set cover, and correlated knapsack cover. We show how to obtain solutions that approximate fully-adaptive solutions using only a few “rounds” of adaptivity. (2) We also study the stochastic score classification problem. We provide the first constant-factor approximation algorithm for this problem, which improves over the previously-known logarithmic approximation ratio. Moreover, our algorithm is non adaptive: it just involves performing tests in a fixed order until the class is identified. (3) For both problems, we present experimental results demonstrating the practical efficacy of our algorithms. We find that a few rounds of adaptivity suffice to obtain high-quality solutions in practice. In the second part of the thesis, we study the K-armed dueling bandits problem, which has applications in a wide-variety of domains like search ranking, recommendation systems and sports ranking where eliciting qualitative feedback is easy while real-valued feedback is not easily interpretable; thus, it has been a popular topic of research in the machine learning community. Previous works have only focused on the sequential setting where the policy adapts after every comparison. However, in many applications such as search ranking and recommendation systems, it is preferable to perform comparisons in a limited number of {parallel} batches. We {introduce} and study the {batched dueling bandits} problem under two standard settings: (i) existence of a Condorcet winner, and (ii) strong stochastic transitivity and stochastic triangle inequality. For both settings, we obtain algorithms with a smooth trade-off between the number of batches and regret. We complement our regret analysis with a nearly-matching lower bound. Finally, in experiments over a variety of real-world datasets, we observe that our algorithm using only a logarithmic number of rounds achieves almost the same performance as fully sequential algorithms (that use T rounds).

Real-time operations management of emerging mobility systems requires designing and developing efficient algorithms to support fast decision-making with provable performance guarantees using minimal resources. This dissertation discusses the challenges of operating ride-hailing systems and centrally-controlled intersections as two examples of large-scale operations in emerging mobility systems and presents policies to improve the system’s performance. The first chapter describes our proposed policy for the operations management of ride-hailing systems. With the development of shared mobility (e.g., ride-hailing systems such as Uber and Lyft), there has been a growing interest in pricing and empty vehicle relocation to maximize system performance. The impatience of passengers during waiting is an important feature of such systems, but it has been neglected in most studies due to the complexities it introduces. In this study, we develop a provably near-optimal dynamic pricing and empty vehicle relocation policy for a ride-hailing system with limited passenger patience. We model the ride-hailing system as a network of double-ended queues. To derive a near-optimal control policy, we first establish a fluid limit of the network in a large market regime where the demand for rides and vehicle supply is large, and show that the fluid-based optimal solution provides an upper bound for the performance of the original ride-hailing system among all dynamic policies. Then, we develop a specific dynamic policy based on the fluid solution for the original problem and investigate the performance of this policy. Among the results, we answer two open questions raised in the literature: (i) the performance of our dynamic policy converges to that of the true optimal value exponentially fast in time when the market size is large [Braverman et al., 2019], and (ii) the passenger loss of our policy decreases to zero exponentially fast when demand size increases [Banerjee et al., 2018a]. Further, we show that our dynamic policy can balance supply utilization and customer waiting times under the Square Root Safety (SRS) rule. The effectiveness of the proposed policy is demonstrated through a numerical experiment using empirical data from DiDi Chuxing. The second chapter investigates the potential of vehicle motion control to improve intersection control. As the bottleneck of transportation networks, the safety and efficiency of transportation networks depend on intersection control. While intersections take up a small portion of the road segments, more than 50% percent of fatal and injury crashes (combined) occur at or near intersections. Intersection control aims to coordinate conflicting traffic movements under safety and kinodynamic constraints in real-time to maximize intersection throughput or minimize traffic delay. This study aims to optimally control intersections to maximize throughput in the presence of trajectory control. These problems have existed as cornerstones of traffic control for over a century. In the current practice, the task is accomplished by heuristic right-of-way allocation rules or principles. For example, traffic signal control has been the primary means of controlling critical intersections with high traffic demand for almost a century. We leverage the graph coloring techniques to devise a control approach that provides an approximation algorithm to the intersection control problem. For an intersection with a sufficiently large footprint, we prove that the proposed algorithm provides a fully polynomial-time approximation scheme for the throughput maximization problem.

This thesis studies online selection problems, with a particular focus on designing constant-competitive algorithms that require less prior information than existing ones. In particular, we present two such algorithms: one for a variant of the matroid secretary problem and the other in the online contention resolution context. The first setting considered in this thesis is based on the matroid secretary problem (MSP). In MSP, elements of a weighted matroid are revealed one by one and the goal is to pick some of them, so that the selection forms an independent set of as large weight as possible. This setting is motivated by applications in online mechanism design and generalizes the classical secretary problem. It was conjectured that, similar to the classical secretary, there exists an algorithm that is constant-competitive for any matroid constraint. Despite the long line of work dedicated to the problem, so far constant competitive ratio has been attained only for certain classes of matroids and for some variations of MSP. One example is the random assignment model (RAMSP), where an adversary fixes a number of weights equal to the ground set size of the matroid, which then get assigned randomly to the elements of the ground set. However, the two known constant-competitive algorithms for this setting, one by Soto (2013) and the other by Oveis Gharan and Vondrák (2013), crucially rely on knowing the full matroid upfront. Lifting this requirement was left as an open question by the aforementioned authors, as there are good arguments for why such assumptions on prior information should be avoided. In this thesis, we present a constant-competitive algorithm for RAMSP that only needs to know the cardinality of the underlying matroid upfront, making RAMSP the first known MSP variant admitting such an algorithm. The second part of the thesis is concerned with random order online contention resolution schemes (ROCRS), which are structured online rounding algorithms with numerous applications and links to other well-known online selection problems. We are specifically interested in ROCRS subject to a matroid constraint, since it is one of the most studied constraint families in the context of contention resolution schemes (CRS) and due to connections to the matroid secretary conjecture. In terms of prior information, most previously known ROCRS rely on knowing both the fractional point to be rounded and the matroid in advance. Since this requirement may limit the scope of application of CRS, one may ask whether good algorithms exist in the absence of prior knowledge. Fu, Lu, Tang, Turkieltaub, Wu, Wu, and Zhang (2022) shed some light on this question by proving that no strong (i.e., constant-selectable) online or even offline contention resolution scheme exists if the fractional point is unknown, not even for graphic matroids. In contrast, we consider a setting where the components of the fractional point are revealed online one by one and provide a simple constant-selectable ROCRS for graphic matroids that only requires to know the size of the ground set in advance. Moreover, our procedure works in a more general setting where the algorithm is allowed to sample a random constant fraction of the elements and then receives all the remaining (non-sampled) elements in adversarial order.

In this thesis, we perform an experimental study of approximation algorithms for the tree augmentation problem (TAP). TAP is a fundamental problem in network design. The goal of TAP is to add the minimum number of edges from a given edge set to a tree so that it becomes 2-edge connected. Formally, given a tree T = (V, E), where V denotes the set of vertices and E denotes the set of edges in the tree, and a set of edges (or links) L ⊆ V × V disjoint from E, the objective is to find a set of edges to add to the tree F ⊆ L such that the augmented tree (V, E ∪ F) is 2-edge connected. Our goal is to establish a baseline performance for each approximation algorithm on actual instances rather than worst-case instances. In particular, we are interested in whether the algorithms rank on practical instances is consistent with their worst-case guarantee rankings. We are also interested in whether preprocessing times, implementation difficulties, and running times justify the use of an algorithm in practice. We profiled and analyzed five approximation algorithms, viz., the Frederickson algorithm, the Nagamochi algorithm, the Even algorithm, the Adjiashivili algorithm, and the Grandoni algorithm. Additionally, we used an integer program and a simple randomized algorithm as benchmarks. The performance of each algorithm was measured using space, time, and quality comparison metrics. We found that the simple randomized is competitive with the approximation algorithms and that the algorithms rank according to their theoretical guarantees. The randomized algorithm is simpler to implement and understand. Furthermore, the randomized algorithm runs faster and uses less space than any of the more sophisticated approximation algorithms.

Abstract: In this study, we present an improved approximation algorithm for three related problems. In the Minimum Sum of Radii clustering problem (MSR), we aim to select k balls in a metric space to cover all points while minimizing the sum of the radii. In the Minimum Sum of Diameters clustering problem (MSD), we are to pick k clusters to cover all the points such that sum of diameters of all the clusters is minimized. At last, in the Minimum Sum of Squared Radii problem (MSSR), the goal is to choose k balls, similar to MSR. However in MSSR, the goal is to minimize the sum of squares of radii of the balls. We present a 3.389-approximation for MSR and a 6.546-approximation for MSD, improving over respective 3.504 and 7.008 developed by Charkar and Panigrahy (2001). In particular, our guarantee for MSD is better than twice our guarantee for MSR. In the case of MSSR, the best known approximation guarantee is 4 ·(540)^2 based on the work of Bhowmick, Inamdar, and Varadarajan in their general analysis of the t-Metric Multicover Problem. With our analysis, we get a 11.078-approximation algorithm for Minimum Sum of Squared Radii.

Abstract: In this thesis, we present a variety of approximation algorithms for Resource Minimization for Fire Containment, Throughput Maximization, and Hierarchical Clustering.Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree $G$, and a vertex $r$ where the fire starts at, called root. At each time step, firefighters can protect up to $B$ vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not been protected so far. The task is to find the smallest $B$ that allows for saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2 even on trees unless P = NP [DM2010]. The main contribution to the RMFC problem is an asymptotic QPTAS for RMFC on trees. More specifically, let $\\epsilon>0$, and $\\mathcal{I}$ be an instance of RMFC where the optimum number of firefighters to save all the leaves is $OPT(\\mathcal{I})$. We present an algorithm which uses at most $\\lceil (1+\\epsilon)OPT(\\mathcal{I})\\rceil$ many firefighters at each time step and runs in time $n^{O(\\log\\log n/\\epsilon)}$. This suggests that the existence of an asymptotic PTAS is plausible especially since the exponent is $O(\\log \\log n)$. Our result combines a more refined height reduction lemma than the one in [SODA2019] with LP rounding and dynamic programming to find the solution. We also apply our height reduction lemma to the algorithm provided in [SODA2019] plus a more careful analysis to improve their 12-approximation and provide a polynomial time ($5+\\epsilon$)-approximation.In Throughput Maximization we have a collection $J$ of $n$ jobs, each having a release time $r_j$, deadline $d_j$, and processing time $p_j$. They have to be scheduled non-preemptively on $m$ identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their $[r_j,d_j]$ window. This problem has been studied extensively (even for the case of $m=1$). Several special cases of the problem remain open. The approximability of the problem for $m=O(1)$ remains a major open question. We study the case of $m=O(1)$ and show that if there are $c$ distinct processing times, i.e. $p_j$'s come from a set of size $c$, then there is a randomized $(1-\\eps)$-approximation that runs in time $O(n^{mc^7\\eps^{-6}}\\log T)$, where $T$ is the largest deadline. Therefore, for constant $m$ and constant $c$ this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning.In Hierarchical Clustering, one is given a set of $n$ data points along with a notion of similarity/dis-similarity between them. More precisely for each two items $i$ and $j$ we are given a weight $w_{i,j}$ denoting their similarity/dis-similarity. The goal is to build a recursive (tree like) partitioning of the data points (items) into successively smaller clusters, which is represented by a rooted tree, where the leaves correspond to the items and each internal node corresponds to a cluster of all the items in the leaves of its subtree. Typically, the goal is to have the items that are relatively similar, to separate at deeper levels of the tree (and hence stay in the same cluster as deep as possible).Dasgupta [STOC2016] defined a cost function for a tree $T$ to be $Cost(T) = \\sum_{i,j \\in [n]} \\big(w_{i,j} \\times |T_{i,j}| \\big)$ where $T_{i,j}$ is the subtree rooted at the least common ancestor of $i$ and $j$ and presented the first approximation algorithm for such clustering.Later Cohen-Addad et al. [JACM2019] considered the same objective function as Dasgupta's but for dissimilarity-based metrics: $Rev(T)=\\sum_{i,j\\in [n]} \\big(w_{i,j}\\times |T_{i,j}|\\big)$,where $w_{i,j}$ is the weight of dissimilarity between two nodes $i$ and $j$. In this version a good clustering should have larger $T_{i,j}$ when $w_{i,j}$ is relatively large. It has been shown that both random partitioning and average linkage have ratio $2/3$ which has been only slightly improved to $0.667078$ [Charikar et al. SODA2020]. Our first main result is to improve this ratio of 0.667078 for $Rev(T)$. We achieve this by building upon the earlier work and use a more delicate algorithm and careful analysis which can be refined to achieve approximation $0.71604$. We also introduce a new objective function for dissimilarity-based Hierarchical Clustering. Consider any tree $T$, we define $H_{i,j}$ as the number of $i$ and $j$'s common ancestors in $T$. In other words, when we think of the process of building tree as a top-down procedure, $H_{i,j}$ is the step in which $i$ and $j$ are separated into two clusters (they were stayed within the same cluster for $H_{i,j}-1$ many steps). We suggest the cost of each tree $T$, which we want to minimize, to be $Cost_H(T) = \\sum_{i,j \\in [n]} \\big(w_{i,j} \\times H_{i,j} \\big)$. We present a $1.3977$-approximation for this objective.

Abstract: In this thesis, we present Approximation Schemes for Capacitated Vehicle Routing Problem (CVRP) on several classes of graphs. In CVRP, introduced by Dantzig and Ramser in 1959, we are given a graph G = (V,E) with metric edges costs, a depot r in V , and a vehicle of bounded capacity Q. The goal is to find a minimum cost collection of tours for the vehicle that return to the depot, each visiting at most Q nodes, such that they cover all the nodes. This generalizes the classic travelling salesman problem (TSP) and has been studied extensively. In the more general setting, each node v has a demand dv and the total demand of each tour must be no more than Q. Either the demand of each node must be served by one tour (unsplittable) or can be served by multiple tour (splittable). The best known approximation algorithm for general graphs has ratio α + 2(1 − ϵ) (for the unsplittable) and α + 1 − ϵ (for the splittable) for some fixed ϵ > 1/3000 , where α is the best approximation for TSP. Even for the case of trees, the best approximation ratio is 4/3 and it has been an open question if there is an approximation scheme for this simple class of graphs. Das and Mathieu presented an approximation scheme with time n^log^O(1/ϵ) n for Euclidean plane R2. No other approximation scheme is known for any other class of metrics (without further restrictions on Q). In this thesis, we make significant progress on this classic problem by presenting Quasi-Polynomial Time Approximation Schemes (QPTAS) for graphs of bounded treewidth, graphs of bounded highway dimensions, and graphs of bounded doubling dimensions. For comparison, our result implies an approximation scheme for Euclidean plane with run time n^O(log^6 n/ϵ^5).

This thesis studies the application of optimization methods in approximating geometric shapes. In particular, it considers the problem of finding maximum volume (axis-aligned) inscribed parallelotopes and boxes in a compact convex set, defined by a finite number of convex inequalities, and presents an optimization approach for solving them. Several optimization models are developed that can be easily generalized to find other inscribed geometric shapes such as triangles, rhombi, and tetrahedrons. To find the largest axis-aligned inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed. Finally, a parametrized optimization approach is developed to find the largest (axis-aligned) inscribed rectangles in the two-dimensional space.

In a typical optimization problem, uncertainty does not depend on the decisions being made in the optimization routine. But, in many application areas, decisions affect underlying uncertainty (endogenous uncertainty), either altering the probability distributions or the timing at which the uncertainty is resolved. Stochastic programming is a widely used method in optimization under uncertainty. Though plenty of research exists on stochastic programming where decisions affect the timing at which uncertainty is resolved, much less work has been done on stochastic programming where decisions alter probability distributions of uncertain parameters. Therefore, we propose methodologies for the latter category of optimization under endogenous uncertainty and demonstrate their benefits in some application areas. First, we develop a data-driven stochastic program (integrates a supervised machine learning algorithm to estimate probability distributions of uncertain parameters) for a wildfire risk reduction problem, where resource allocation decisions probabilistically affect uncertain human behavior. The nonconvex model is linearized using a reformulation approach. To solve a realistic-sized problem, we introduce a simulation program to efficiently compute the recourse objective value for a large number of scenarios. We present managerial insights derived from the results obtained based on Santa Fe National Forest data. Second, we develop a data-driven stochastic program with both endogenous and exogenous uncertainties with an application to combined infrastructure protection and network design problem. In the proposed model, some first-stage decision variables affect probability distributions, whereas others do not. We propose an exact reformulation for linearizing the nonconvex model and provide a theoretical justification of it. We designed an accelerated L-shaped decomposition algorithm to solve the linearized model. Results obtained using transportation networks created based on the southeastern U.S. provide several key insights for practitioners in using this proposed methodology. Finally, we study submodular optimization under endogenous uncertainty with an application to complex system reliability. Specifically, we prove that our stochastic program's reliability maximization objective function is submodular under some probability distributions commonly used in reliability literature. Utilizing the submodularity, we implement a continuous approximation algorithm capable of solving large-scale problems. We conduct a case study demonstrating the computational efficiency of the algorithm and providing insights.

In real life, many combinatorial optimization problems are solved by simple algorithms (e.g., greedy, local search, thresholding, etc.) without any provable guarantees on the performance of the returned solution compared to the optimal one. Even though theoretical computer scientists have established strong results for the performance of such algorithms in diverse settings, it is not always easy to match the real life application to one of those well-studied problems. That said, we also have power systems which is a rich source of combinatorial optimization problems. The combinatorial nature arises whether it is turning switches on or off, assigning generation to different sources, scheduling charging or discharging of electric vehicles, splitting loads between different phases, or installing equipment at certain locations of the grid. On top of the combinatorial nature, these applications usually entail another level of complexity due to the nonlinearity of their objective and/or constraints. In this Ph.D. dissertation, I will try to bridge theoretical computer science and power systems by utilizing tools from approximation algorithms and mechanism design to provide rigorous guarantees for three problems in power systems. Contributing to the intersection of these two fields is important to both push the state-of-the-art approximation algorithms by introducing new problems that cannot be solved with existing techniques, as well as provide methods for both scalable and rigorous solutions to problems arising in real-world power systems. In the first problem, the goal is to minimize the power loss in a distribution network via changing the on/off status of switches in the network. Bringing to bear recent advances in submodular optimization, we derive performance bounds for a simple local-search algorithm that has been used in practice for a long time. We then focus on special properties of the grid that let us develop tailored algorithms with improved performance guarantees. Finally, we use our insights from our theoretical analysis to propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance. In the second problem, we propose a novel way to use electric vehicles as dynamic energy storage for supporting the power grid, by discharging them at designated times and locations of need. We show that the underlying scheduling problem is NP-hard and propose various approximation algorithms with different performance guarantees. Finally in the last problem, we study a mechanism design problem for a system operator who wants to optimally assign the demand to different energy generators. We study this as a dynamic procurement auction, in which the generators may go out of business if they are not frequently picked. Since this will increase the electricity price in the long term, the system operator has to design a mechanism that minimizes the overall cost via selecting different sources frequent enough to maintain the competition. We show how to obtain optimal thresholding mechanisms via a greedy approach.

In real life, many combinatorial optimization problems are solved by simple algorithms (e.g., greedy, local search, thresholding, etc.) without any provable guarantees on the performance of the returned solution compared to the optimal one. Even though theoretical computer scientists have established strong results for the performance of such algorithms in diverse settings, it is not always easy to match the real life application to one of those well-studied problems. That said, we also have power systems which is a rich source of combinatorial optimization problems. The combinatorial nature arises whether it is turning switches on or off, assigning generation to different sources, scheduling charging or discharging of electric vehicles, splitting loads between different phases, or installing equipment at certain locations of the grid. On top of the combinatorial nature, these applications usually entail another level of complexity due to the nonlinearity of their objective and/or constraints. In this Ph.D. dissertation, I will try to bridge theoretical computer science and power systems by utilizing tools from approximation algorithms and mechanism design to provide rigorous guarantees for three problems in power systems. Contributing to the intersection of these two fields is important to both push the state-of-the-art approximation algorithms by introducing new problems that cannot be solved with existing techniques, as well as provide methods for both scalable and rigorous solutions to problems arising in real-world power systems. In the first problem, the goal is to minimize the power loss in a distribution network via changing the on/off status of switches in the network. Bringing to bear recent advances in submodular optimization, we derive performance bounds for a simple local-search algorithm that has been used in practice for a long time. We then focus on special properties of the grid that let us develop tailored algorithms with improved performance guarantees. Finally, we use our insights from our theoretical analysis to propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance. In the second problem, we propose a novel way to use electric vehicles as dynamic energy storage for supporting the power grid, by discharging them at designated times and locations of need. We show that the underlying scheduling problem is NP-hard and propose various approximation algorithms with different performance guarantees. Finally in the last problem, we study a mechanism design problem for a system operator who wants to optimally assign the demand to different energy generators. We study this as a dynamic procurement auction, in which the generators may go out of business if they are not frequently picked. Since this will increase the electricity price in the long term, the system operator has to design a mechanism that minimizes the overall cost via selecting different sources frequent enough to maintain the competition. We show how to obtain optimal thresholding mechanisms via a greedy approach.

In the field of multiagent systems, one important problem is fairly allocating items among a set of agents. The gold standard fairness property is envy-freeness whereby each agent prefers the bundle allocated to them over any other bundle. For indivisible goods, envy-freeness cannot be guaranteed: consider two agents and one item. In the context of indivisible goods, one key fairness notion which has gained significant attention in recent years is the maximin share guarantee (MMS). MMS extends the cut-and-choose protocol to multiple agents by guaranteeing each agent as much value as if they divided items into bundles but chose last. However, MMS is not guaranteed to exist, and even it exists, computing an MMS allocation is computationally hard. Consequently, several approximation techniques were proposed to ensure all agents receive a fraction of their MMS. We propose an orthogonal approximation which aims to guarantee MMS for a fraction of the agents. We construct instances where any optimal approximation algorithm fails to guarantee MMS for most agents. We show how to interpolate between the fraction of agents and the fraction of MMS guaranteed to agents. We prove the existence of allocations which satisfy 2/3 of the agents. Our algorithmic technique immediately implies a polynomial-time algorithm for any number of items when there are less than nine agents. Our results significantly reduce the existence gap of MMS when agents divide the items into 3n/2 bundles. We empirically demonstrate that our algorithm outperforms its worst-case bounds in practice on both synthetic and real-world data. We extend our discussion of maximin share approximations to chores. We extend many of the techniques used for MMS approximations to the chores setting. Using these new techniques, we prove the existence of allocations which satisfy all agents when they expect to divide the workload among 2n/3 agents.

The analysis of graphs and finding matchings and its generalization to b-matchings in a graph have numerous real-world applications. Given a mapping b of the vertex set of a graph G to the nonnegative integers, a perfect b-matching is a mapping M from the edge set to the nonnegative integers such the sum of the b-values over all edges incident with each vertex v equals b(v). Two b-matchings are independent if their supports, i.e., edges with nonzero b-values, are disjoint. In this thesis we show that the problem of determining the existence of two independent perfect b-matchings is NP-complete, even when restricted to the complete graph. However, in the case where no b-value is too large, i.e., at most one-sixth the sum of the b-values over all the vertices, we present an O(n log n) algorithm for computing two independent perfect b-matchings in the complete graph, where n denotes the number of vertices. In addition, we present an efficient approximation algorithm b-dominator for maximum b-matchings with application to computing an approximation to independent maximum b-matchings. In this thesis, we report on empirical research we conducted on how good of an approximation was achieved. Our results show that algorithm b-dominator performed best when the variance in the degree of the vertices is low, the average degree is sufficiently large and the 2-hop cover of the vertices is evenly distributed over the graph. Finally, we discuss the possibility of using algorithm b-dominator for reliable peer-to-peer network backup.

Abstract: Scheduling problems are problems to assign jobs to machines at particular times while trying to optimize some objective function. In this work, we study one such problem, called Generalized Path Scheduling (GPS) problem, in which the machines form a path and each job is assigned a subpath of machines to be processed on. We consider minimizing makespan (largest completion time) and/or total completion time and we present several improved approximation algorithms for both objectives.

In online retailing, core operational questions include deciding on the assortment of products that should be displayed to incoming customers and how to adjust these assortments and prices in real-time according to current capacity and observed demand. In this dissertation, we explore three new developments in online retailing and develop models and techniques for revenue management in these settings. The underlying goal in each of the chapters is to develop computationally efficient and provably good algorithms. First, we consider a revenue management model over a single flight leg, where customers are allowed to lock an available fare. The goal is to find a policy to decide which set of fare classes to make available at each time period to maximize the total expected revenue. We develop an approximate policy that is guaranteed to obtain at least half of the optimal total expected revenue. Second, we consider dynamic assortment problems with reusable products, in which each arriving customer chooses a product within an offered assortment, uses the product for a random duration of time, and returns the product back to the firm to be used by other customers. The goal is to find a policy for deciding on the assortment to offer to each customer so that the total expected revenue over a finite selling horizon is maximized. We present an approximate policy that is guaranteed to obtain at least half of the optimal total expected revenue. The policy is based on constructing linear approximations to the optimal value functions. Lastly, we examine the revenue-utility assortment problem with the goal of finding an assortment that maximizes a linear combination of the expected revenue of the firm and the expected utility of the customer. This criterion captures the tradeoff between the firm-centric objective of maximizing the expected revenue and the customer-centric objective of maximizing the expected utility. When customers choose according to the multinomial logit model, and there is a constraint on the offered assortments characterized by a totally unimodular matrix, finding the optimal assortment requires solving a nonconcave optimization problem. We provide an efficient algorithm for finding the welfare optimal assortment by solving a parametric linear program and testing a polynomial size collection of candidate assortments.

Outdoor autonomous robots carrying sensors have the potential to provide transformative data for science, industry, and safety. However, limited battery life is a factor that restricts their wide deployment. To fully realize the potential of these robots, this restriction must be loosened. We improve battery life by designing algorithms that allow outdoor sensors to intelligently plan their movements to minimize power consumption while taking the necessary measurements for their tasks. This dissertation focuses on three main problems: The first problem we address is the problem of planning energy-minimal trajectories for solar-powered robots in a cluttered environment that contains shadows. We make contributions to this problem in both planning and estimation. We present a novel planning algorithm that efficiently computes an optimal trajectory on a discretized grid, given a solar map and a target position. We also present three methods of estimating the solar map that relates position and time with the amount of solar energy that can be collected if the robot is in that position at that time, using only previous measurements of solar power tagged with positions and times. The first method uses Gaussian Process regression to directly predict the solar power at a position based on neighboring measurements. The second method uses spatiotemporal Gaussian Process classification to estimate the likelihood that a particular position will be in the sun. The third method uses the measurements of sun and shade to infer shadow-casting objects, and performs raytracing through the uncertain height map to estimate the likely solar map for any given sun angle. These methods are justified through field experiments and in simulation. The second problem we address is the problem of exploring unknown environments in a manner that guarantees bounded motion cost. We consider two variants of this problem. First we consider a boat, equipped with a sonar sensor, that encounters an obstacle while it is attempting to reach a destination. Second we consider a solar-powered vehicle attempting to map the shadows in an environment. For both variants, we present online algorithms and examine their performance using competitive analysis. In competitive analysis, the performance of an online algorithm is compared against the optimal offline algorithm. For obstacle avoidance, the offline algorithm knows the shape of the obstacle. For solar exploration, the offline algorithm knows the geometry of the shadow casting objects. We obtain an O(1) competitive ratio for obstacle avoidance, and an O(log n) competitive ratio for solar exploration, where n is the number of critical points to observe. The strategies for obstacle avoidance are validated through extensive field experiments, and the strategies for exploration are validated with simulations. The third problem we address is a novel coverage problem that arises in aerial surveying applications. The goal is to compute a shortest path that visits a given set of cones--this is the path that maximizes the coverage ability for a UAV with a limited battery size. The apex of each cone is restricted to lie on the ground plane. The common angle alpha of the cones represent the field of view of the onboard camera. The cone heights, which can be varying, correspond with the desired observation quality (e.g. resolution). This problem is a novel variant of the Traveling Salesman Problem with Neighborhoods (TSPN), and we call it Cone-TSPN. Our main contribution is a polynomial time approximation algorithm for Cone-TPSN. We analyze its theoretical performance and show that it returns a solution whose length is at most O(1 + log(hmax/hmin)) times the length of the optimal solution where hmax and hmin are the heights of the tallest and shortest input cones, respectively. We demonstrate the use of our algorithm in a representative precision agriculture application. We further study its performance in simulation using randomly generated cone sets. Our results indicate that the performance of our algorithm is superior to standard solutions. The results in this dissertation have advanced the state of the art in planning energy-minimizing trajectories for outdoor vehicles, by presenting algorithms with strong theoretical guarantees, justified in field experiments and simulations.

This dissertation aims to consider different problems in the area of stochastic optimization, where we are provided with more information about the instantiation of the stochastic parameters over time. With uncertainty being an inseparable part of every industry, several applications can be modeled as discussed. In this dissertation we focus on three main areas of applications: 1) ranking problems, which can be helpful for modeling product ranking, designing recommender systems, etc., 2) routing problems which can cover applications in delivery, transportation and networking, and 3) classification problems with possible applications in medical diagnosis and chemical identification. We consider three types of solutions for these problems based on how we want to deal with the observed information: static, adaptive and a priori solutions. In Chapter II, we study two general stochastic submodular optimization problems that we call Adaptive Submodular Ranking and Adaptive Submodular Routing. In the ranking version, we want to provide an adaptive sequence of weighted elements to cover a random submodular function with minimum expected cost. In the routing version, we want to provide an adaptive path of vertices to cover a random scenario with minimum expected length. We provide (poly)logarithmic approximation algorithms for these problems that (nearly) match or improve the best-known results for various special cases. We also implemented different variations of the ranking algorithm and observed that it outperforms other practical algorithms on real-world and synthetic data sets. In Chapter III, we consider the Optimal Decision Tree problem: an identification task that is widely used in active learning. We study this problem in presence of noise, where we want to perform a sequence of tests with possible noisy outcomes to identify a random hypothesis. We give different static (non-adaptive) and adaptive algorithms for this task with almost logarithmic approximation ratios. We also implemented our algorithms on real-world and synthetic data sets and compared our results with an information theoretic lower bound to show that in practice, our algorithms' value is very close to this lower bound. In Chapter IV, we focus on a stochastic vehicle routing problem called a priori traveling repairman, where we are given a metric and probabilities of each vertices being active. We want to provide an a priori master tour originating from the root that is shortcut later over the observed active vertices. Our objective is to minimize the expected total wait time of active vertices, where the wait time of a vertex is defined as the length of the path from the root to this vertex. We consider two benchmarks to evaluate the performance of an algorithm for this problem: optimal a priori solution and the re-optimization solution. We provide two algorithms to compare with each of these benchmarks that have constant and logarithmic approximation ratios respectively.

Integer programming formulations play a key role in the design of efficient algorithms and approximation algorithms for many discrete linear optimization problems as found in previous research. A specific integer programming formulation of a discrete linear optimization problem may lead to algorithms with better running time or approximation algorithms with better approximation factors than the other algorithms for the same problem. Inspired by this, we introduce here new integer programming formulations to devise efficient algorithms and approximation algorithms for two classes of problems, the covariate balancing problems and the Replenishment Storage problems.The existence of certain special integer programming formulations is an evidence of the existence of polynomial time algorithms for some discrete optimization problems. For a variant of the covariate balancing problems, our new integer programming formulation has a network structure that was not previously known. We use this new formulation to devise network flow algorithms, which have better running time than an existing polynomial time algorithm. Other integer programming formulations we introduce show that several variants of the class of covariate balancing problems are fixed-parameter tractable. Integer programming formulations are often important in designing approximation algorithms for intractable problems. The Replenishment Storage problems were known to be NP-hard and one approximation algorithm was known for a special variant of the class. We derive for this variant a polynomial time approximation scheme using a new integer programming formulation. Our new formulation also leads to the first known approximation scheme for another variant of this class. Moreover, this resolves the complexity status of some variants of the Replenishment Storage problems as weakly NP-hard.

Over the past 30 years, the study of counting problems has become an interesting and important work. The framework of counting problems can capture applications in diverse fields, such as graph colouring and homomorphism in graph theory, and the Ising and Potts model from statistical physics. In this thesis, we will discuss my recent research work focusing on this area. In Chapter 1, the basic notions and definitions of counting problems will be introduced. Because of the hardness result of computation complexity for counting problems, we will mainly consider whether we have efficient approximation algorithms for counting problems. In the algorithmic part, one of the most exciting research is to establish the connection between the uniqueness phase transition of spin systems and the approximability phase transition of computing partition functions. In Chapter 2, we first discuss some basic methods of designing approximation algorithms, including the connection between sampling and counting and the correlation decay approach. These methods will be used in Chapter 4 and 5. In Chapter 3, we will discuss the uniqueness threshold for the antiferromagnetic Potts model on d-ary trees and introduce our results for small q. Chapter 4 and 5 contain two examples of counting and sampling in the uniqueness regime. We designed approximation algorithms for counting the number of 4-colourings on cubic graphs and sampling from the Potts model on random regular graphs in the uniqueness regime. In the complexity part, a classification result for the complexity of approximate counting Boolean Constraint Satisfaction Problems on bounded-degree instances will be introduced in Chapter 6. We focused on whether, for all Boolean constraint languages Γ, there is a “barrier” value ∆0 such that for all ∆ > ∆0, the counting problem of Boolean CSP is computationally hard to approximate, and completely classified the complexity of this problem.

Abstract: Scheduling problems are problems in which jobs are assigned to machines at particular times. A common objective of scheduling is to schedule as many jobs before their deadline as possible, called Throughput Maximization. In this thesis, we provide algorithms for various cases of Throughput Maximization scheduling problems, varying bounds on the number of release times, job sizes, deadlines, and even the number of release times the release time and deadlines of a job can span across.In Chapter 2, we examine the case where both the number of job sizes and the number of release times is bounded by a constant value. This result is progress to closing a known open problem of Throughput Maximization with only constant sized job sizes [20]. This algorithm is a dynamic program that relies on a framework based around what is known as the Jackson Rule or Earliest Due Date ordering [13]. In Chapter 3, we consider the case of Throughput Maximization where the number of release times and deadlines are bounded by a constant value on a constant number of machines. In this Chapter we find a pseudo-polynomial time exact algorithm that we extend to a PTAS. This algorithm exploits the fact that we can partition the schedule into intervals between two consecutive release times or deadlines, which allows us to assign jobs to each of these intervals in polynomial time. We also extend the show that this case is NP-Complete by a reduction from the Partition problem. In Chapter 4, we present the most general result in this thesis by finding a pseudo-polynomial time algorithm for the case of Throughput Maximization where the only restriction is that there are a constant number of release times, which we extend to the case where the interval between a jobs release time and deadlines has only a constant number of release times, called the span. This algorithm makes use of similar approach to that of Chapter 3, in that we can partition jobs to intervals between consecutive release times and find the schedule interval by interval. The result for the constant span, we use the first algorithm of this chapter as a subroutine over the maximum span of release times

Abstract: Many real-world problems can be formulated as combinatorial optimization problems, thus making it very important to find efficient methods to solve them, both theoretically and practically. In this thesis, we consider several NP-hard combinatorial optimization problems, consisting of some classification problems and some computational biology problems, all of which can be formulated in terms of graphs; we focus on the design and analysis of approximation algorithms for these problems. The main techniques used to design and analyze approximation algorithms in this thesis include: randomized rounding (based on linear programming relaxation), local search, and amortization.We investigate the following NP-hard problems in this thesis: the maximum happy vertice (MHV) problem, its complement the minimum unhappy vertices (MUHV) problem, the maximum duo-preservation string mapping (Max-Duo) problem, and the k-path-partition (k-PP) problem. The MHV and MUHV problems, which are actually labeling problems, and the k-PP problem can all be considered as classification problems. The Max-Duo problem isa string comparison problem, with applications in bioinformatics and data compression, and the k-PP problem was actually arising from a broadcasting problem in data communication networks. We present approximation algorithms for MHV and MUHV based on randomized linear programming rounding. For Max-Duo and k-PP with k = 3, we propose improved approximation algorithms mainly based on local search, and the performances of these approximation algorithms are all done through amortized analysis.

In this dissertation, we study two problems that have the theme of extracting information from lower dimensional samples. A number of recent works have studied algorithms for entrywise $\ell_p$-\emph{low rank approximation}, namely algorithms which given an $n \times d$ matrix $A$ (with $n \geq d$), output a rank-$k$ matrix $B$ minimizing $\|A-B\|_p^p=\sum_{i,j} |A_{i,j} - B_{i,j}|^p$ when $p > 0$; and $\|A-B\|_0 = \sum_{i,j} [A_{i,j} \neq B_{i,j}]$ for $p=0$, where $\|A-B\|_0$ denotes the number of entries $(i,j)$ for which $A_{i,j} \neq B_{i,j}$.For $p = 1$, this is often considered more robust than the SVD, while for $p = 0$ this corresponds to minimizing the number of disagreements, or robust PCA. This problem is known to be NP-hard for $p \in \{0,1\}$, already for $k = 1$, and while there are polynomial time approximation algorithms, their approximation factor is at best $\poly(k)$. It was left open if there was a polynomial-time approximation scheme (PTAS) for $\ell_p$-approximation for any $p \geq 0$. We show the following:\begin{enumerate} \item On the algorithmic side, for $p \in (0,2)$, we use a technique called \emph{sketching} to give the first $n^{\poly(k/\eps)}$ time $(1+\eps)$-approximation algorithm. For $p = 0$, there are various problem formulations, a common one being the binary setting for which $A\in\{0,1\}^{n\times d}$ and $B = U \cdot V$, where $U\in\{0,1\}^{n \times k}$ and $V\in\{0,1\}^{k \times d}$. For this setting, we obtain an algorithm with time $n \cdot d^{\poly(k/\eps)}$. \item On the hardness front, for $p \in (1,2)$, we show under the Small Set Expansion Hypothesis and Exponential Time Hypothesis (ETH), there is no constant factor approximation algorithm running in time $2^{k^{\delta}}$ for a constant $\delta > 0$, showing an exponential dependence on $k$ is necessary. We also show for finite fields of constant size, under the ETH, that any fixed constant factor approximation algorithm requires $2^{k^{\delta}}$ time for a constant $\delta > 0$.\end{enumerate} \emph{Population recovery} is the problem of learning an unknown distribution over an unknown set of $n$-bit strings, given access to independent \emph{traces} from the distribution that have been independently corrupted according to some noise channel. Recent work has intensively studied such problems both for the {bit-flip} noise channel and for the erasure noise channel. In this dissertation we initiate the study of population recovery under the \emph{deletion channel}, in which each bit $b$ is independently \emph{deleted} with some fixed probability and the surviving bits are concatenated and transmitted. This is a far more challenging noise model than bit-flip~noise or erasure noise; indeed, even the simplest case in which the population is of size 1 (corresponding to a trivial probability distribution supported on a single string) corresponds to the \emph{trace reconstruction} problem, which is a challenging problem that has received much recent attention. In this work we give algorithms and lower bounds for population recovery under the deletion channel when the population size is some value $\ell > 1$. As our main sample complexity upper bound, we show that for any population size $\ell = o(\log n / \log \log n)$, a population of $\ell$ strings from $\zo^n$ can be learned under deletion channel noise using $\smash{2^{n^{1/2 + o(1)}}}$ samples. On the lower bound side, we show that at least $n^{\Omega{(\ell)}}$ samples are required to perform population recovery under the deletion channel when the population size is $\ell$, for all $\ell \leq n^{1/2 - \epsilon}$.

In this dissertation we examine two topics relevant to modern machine learning research: 1) Subgraph counting and 2) High-dimensional subset selection. The former can be used to construct features for performing graph analytics. The latter has applications in sparse modeling such as feature selection, sparse regression, and interpretable machine learning. Since these problems become intractable for large datasets, we design efficient approximation algorithms for both tasks with data-dependent performance guarantees. In the first part of the dissertation, we study the problem of approximating all three and four node induced subgraphs in a large graph. These counts are called the 3 and 4-profile, respectively, and describe a graph's connectivity properties. This problem generalizes graphlet counting and has found applications ranging from bioinformatics to spam detection. Our algorithms use the novel concept of graph profile sparsifiers: sparse graphs that can be used to approximate the full profile counts for a given large graph. We obtain novel concentration results showing that graphs can be substantially sparsified and still retain good approximation quality for the global graph profile. We also study the problem of counting local and ego profiles centered at each vertex of the graph. These quantities embed every vertex into a low-dimensional space that characterizes the local geometry of its neighborhood. We introduce the concept of edge pivots and show that all local 3 and 4-profiles can be computed as vertex programs using compressed two-hop information. Our algorithms are local, distributed message-passing schemes and compute all graph profiles in parallel. We empirically evaluate these algorithms with a distributed GraphLab implementation, and show improvements over previous state-of-the-art in experiments scaling up to 640 cores on Amazon EC2. In the second part we shift to the problem of subset selection: for example, selecting a few features from a large feature set. Motivated by the need for interpretable, nonlinear regression models for high-dimensional data, we draw a novel connection between this and submodular maximization. We extend an earlier concept of weak submodularity from the setting of sparse linear regression to a broad class of objective functions, including generalized linear model likelihoods. We then show that three greedy algorithms (Oblivous, Forward Stepwise, and Orthogonal Matching Pursuit) perform within a constant factor from the best possible subset. Our methods do not require any statistical modeling assumptions and allow direct control over the number of obtained features. This contrasts with other work that uses regularization parameters to control sparsity only implicitly. Our proof technique connecting convex analysis and submodular set function theory may be of independent interest for other statistical learning applications that have combinatorial structure. In the third part, we consider the problem of explaining the predictions of a given black-box classifier. For example, why does a deep neural network assign an image to a particular class? We cast interpretability of black-box classifiers as a subset selection problem and propose to solve it with an efficient streaming algorithm. We provide a constant factor approximation guarantee for this algorithm in the case of a random stream order and a weakly submodular objective function. This is the first such theoretical guarantee for this general class of functions, and we also show that no such algorithm exists for a worst case stream order. Our algorithm obtains similar explanations of Inception V3 predictions 10 times faster than the state-of-the-art LIME framework.

In this dissertation we examine two topics relevant to modern machine learning research: 1) Subgraph counting and 2) High-dimensional subset selection. The former can be used to construct features for performing graph analytics. The latter has applications in sparse modeling such as feature selection, sparse regression, and interpretable machine learning. Since these problems become intractable for large datasets, we design efficient approximation algorithms for both tasks with data-dependent performance guarantees. In the first part of the dissertation, we study the problem of approximating all three and four node induced subgraphs in a large graph. These counts are called the 3 and 4-profile, respectively, and describe a graph's connectivity properties. This problem generalizes graphlet counting and has found applications ranging from bioinformatics to spam detection. Our algorithms use the novel concept of graph profile sparsifiers: sparse graphs that can be used to approximate the full profile counts for a given large graph. We obtain novel concentration results showing that graphs can be substantially sparsified and still retain good approximation quality for the global graph profile. We also study the problem of counting local and ego profiles centered at each vertex of the graph. These quantities embed every vertex into a low-dimensional space that characterizes the local geometry of its neighborhood. We introduce the concept of edge pivots and show that all local 3 and 4-profiles can be computed as vertex programs using compressed two-hop information. Our algorithms are local, distributed message-passing schemes and compute all graph profiles in parallel. We empirically evaluate these algorithms with a distributed GraphLab implementation, and show improvements over previous state-of-the-art in experiments scaling up to 640 cores on Amazon EC2. In the second part we shift to the problem of subset selection: for example, selecting a few features from a large feature set. Motivated by the need for interpretable, nonlinear regression models for high-dimensional data, we draw a novel connection between this and submodular maximization. We extend an earlier concept of weak submodularity from the setting of sparse linear regression to a broad class of objective functions, including generalized linear model likelihoods. We then show that three greedy algorithms (Oblivous, Forward Stepwise, and Orthogonal Matching Pursuit) perform within a constant factor from the best possible subset. Our methods do not require any statistical modeling assumptions and allow direct control over the number of obtained features. This contrasts with other work that uses regularization parameters to control sparsity only implicitly. Our proof technique connecting convex analysis and submodular set function theory may be of independent interest for other statistical learning applications that have combinatorial structure. In the third part, we consider the problem of explaining the predictions of a given black-box classifier. For example, why does a deep neural network assign an image to a particular class? We cast interpretability of black-box classifiers as a subset selection problem and propose to solve it with an efficient streaming algorithm. We provide a constant factor approximation guarantee for this algorithm in the case of a random stream order and a weakly submodular objective function. This is the first such theoretical guarantee for this general class of functions, and we also show that no such algorithm exists for a worst case stream order. Our algorithm obtains similar explanations of Inception V3 predictions 10 times faster than the state-of-the-art LIME framework.

In this thesis we study fundamental problems that arise in optimization and its applications. We present provably efficient algorithms that achieve better running times or approximation guarantees than previously known. Our method draws on the toolkit from convex and combinatorial optimization as well as economics. By intertwining techniques from these disciplines, we are able to make progress on multiple old and new problems, some of which have stood open for many years. Main results of this thesis include the following:Convex Programming: We show how to solve convex programming with an expected O(n log(nR/\epsilon)) evaluations of the separation oracle and additional time O(n^3\log^{O(1)}(nR/\epsilon)). This matches the oracle complexity and improves upon the O(n^{\omega+1}\log(nR/\epsilon)) additional time of the previous fastest algorithm achieved over 25 years ago for the current value of the matrix multiplication constant when R/\epsilon=O(\poly(n)).Submodular Function Minimization: We provide new weakly and strongly polynomial time algorithms with a running time of O(n^{2}\log nM\cdot\text{EO}+n^{3}\log^{O(1)}nM) and O(n^{3}\log^{2}n\cdot\text{EO}+n^{4}\log^{O(1)}n), improving upon the previous best of O((n^{4}\cdot\text{EO}+n^{5})\log M) and O(n^{5}\cdot\text{EO}+n^{6}) respectively. We also provide the first subquadratic time algorithm for computing an approximately optimal solution.Matroid Intersection: We provide new algorithms with a running time of O(nr\mathcal{T_{\text{rank}}}\log n\log(nM)+n^{3}\log^{O(1)}nM) and O(n^{2}\mathcal{T_{\text{ind}}}\log(nM)+n^{3}\log^{O(1)}nM , achieving the first quadratic bound on the query complexity for the independence and rank oracles. In the unweighted case, this is the first improvement since 1986 for independence oracle.Submodular Flow: We obtain a faster weakly polynomial running time of O(n^{2}\log(nCU)\cdot\EO+n^{3}\log^{O(1)}(nCU)), improving upon the previous best of O(mn^{5}\log(nU)\cdot\EO) and O\left(n^{4}h\min\left\{ \log C,\log U\right\} \right) from 15 years ago by a factor of \tilde{O}(n^{4}).Semidefinite Programming: We obtain a running time of \tilde{O}(n(n^{2}+m^{\omega}+S)), improving upon the previous best of \tilde{O}(n(n^{\omega}+m^{\omega}+S)) for the regime S is small.Market Equilibrium: We present the first polynomial time algorithm for computing market equilibrium in an economy with indivisible goods and general buyer valuations having only access to an aggregate demand oracle.Vertex Cover with Hard Capacity: We give a f-approximation algorithm for the minimum unweighted Vertex Cover problem with Hard Capacity constraints on f-hypergraphs This improves over the previous 2f-approximation and is the best possible assuming the unique game conjecture.Network Design for Effective Resistance: We initiate the study of network design for s-t effective resistance. Among other results we present a constant factor approximation by applying classic techniques to a convex quadratic programming relaxation.

This thesis addresses clustering problems in two distinct settings. In the first setting we explore the notion of what it means for a graph to admit a good partition into k-clusters. We say a partition of a graph is strong if each cluster has small external conductance, and large internal conductance. We consider a natural embedding of the graph into Rk involving the first k eigenvectors of the graph's Laplacian matrix. We show that for graphs which admit a sufficiently strong k-partition, much of the l2-mass of each partition element concentrates around a distinct point in the embedding. Further, we show how to estimate the degree of concentration as well as the separation of the k embedding points from the input graph. We exploit this fact to design a simple greedy spectral clustering algorithm, spectral k-clustering, which returns a partition that is provably close to a strong partition, provided that the input graph admits one. A recent result shows that strong partitions exist for graphs with a sufficiently large spectral gap between the k-th and (k+1)-st eigenvalues. Taking this together with our main theorem gives a spectral algorithm which finds a good partition in graphs with a sufficiently large spectral gap. Finally, we provide an experimental evaluation of the algorithm on inputs which do not necessarily satisfy the conditions required by our theorems.The second setting concerns metric spaces which change over time. Here, our goal is to find a temporally coherent clustering. We introduce a framework for clustering finite sequences of metric spaces taken from a common ambient metric space and study generalizations of some classic clustering problems to this setting. Formally, let P denote this sequence of metric subspaces, which we call a temporal-sampling. Given a collection of clusters, C, we quantify the quality of the clustering under multiple objectives: complexity (size, |.|), a spatial clustering cost (μ), and a temporal cost (δ) which is small when the clusters exhibit good locality. For a fixed choice of objectives, we say that a temporal-sampling admits a temporal (k, r, δ)-clustering for some k in N, r in R≥0, δ in R≥0 if there exists a clustering C of P such that |C| , μ(C) , and δ(C) . For certain choices of objectives, we study the problem of deciding in polynomial-time whether or not a temporal-sampling admits a temporal (k, r, δ)-clustering when k, r, and δ are taken to be some functions of the input. Further, let α, β, γ be positive real numbers which are all at least 1. An algorithm is a temporal (α, β, γ)-approximation if it is guaranteed to return a temporal (α k, β r, γ δ)-clustering whenever P admits a temporal (k, r, δ)-clustering. We study the existence of polynomial-time temporal (α, β, γ)-approximations under various assumptions. We give several approximation algorithms of this kind and exhibit some conditions under which approximation is NP-hard. Last, we introduce a model for hierarchical temporal clusterings and give a polynomial-time approximation algorithm.

Abstract: Budgeted Red-Blue Median is a generalization of classic k-Median in that there are two sets of facilities, say R and B, that can be used to serve clients located in some metric space. The goal is to open kr facilities in R and kb facilities in B for some given bounds kr,kb and connect each client to their nearest open facility in a way that minimizes the total connection cost.

We design new and improved approximation algorithms for classical problems in machine scheduling and resource allocation. In the machine scheduling problem we consider, we are given a set of jobs $J$ with processing times $p_j$ for each $j \in J$. Further, a job $j$ may be scheduled only on some subset of machines $S_j \subseteq M$. The goal is to find an assignment of jobs to machines to minimize the time by which all jobs can be processed. The input for the resource allocation problem we consider is identical after treating the jobs as resources and machines as players respectively. The goal, however, is different: we want to assign resources to the players while ensuring that every player receives resources totaling value at least $\tau$ for the largest possible $\tau$. This corresponds to maximizing a natural notion of fairness. Our techniques for improving the state of the art for both problems are versatile. We demonstrate their applicability in developing an efficient hypergraph generalization of the Hungarian algorithm for finding perfect matchings in bipartite graphs.

Semidenite programming (SDP) relaxations have been a popular choice for approximationalgorithm design ever since Goemans and Williamson used one to improve the best approximationof Max-Cut in 1992. In the effort to construct stronger and stronger SDP relaxations,the Sum-of-Squares (SOS) or Lasserre hierarchy has emerged as the most promisingset of relaxations. However, since the SOS hierarchy is relatively new, we still do not knowthe answer to even very basic questions about its power. For example, we do not even knowwhen the SOS SDP is guaranteed to run correctly in polynomial time!In this dissertation, we study the SOS hierarchy and make positive progress inunderstanding the above question, among others. First, we give a sufficient, simple criteriawhich implies that an SOS SDP will run in polynomial time, as well as confirm that ourcriteria holds for a number of common applications of the SOS SDP. We also present anexample of a Boolean polynomial system which has SOS certificates that require exponential time to find, even though the certificates are degree two. This answers a conjecture of [54].Second, we study the power of the SOS hierarchy relative to other symmetric SDP relaxationsof comparable size. We show that in some situations, the SOS hierarchy achievesthe best possible approximation among every symmetric SDP relaxation. In particular, weshow that the SOS SDP is optimal for the Matching problem. Together with an SOS lowerbound due to Grigoriev [32], this implies that the Matching problem has no subexponentialsize symmetric SDP relaxation. This can be viewed as an SDP analogy of Yannakakis'original symmetric LP lower bound [72].As a key technical tool, our results make use of low-degree certificates of ideal membershipfor the polynomial ideal formed by polynomial constraints. Thus an important step in ourproofs is constructing certificates for arbitrary polynomials in the corresponding constraintideals. We develop a meta-strategy for exploiting symmetries of the underlying combinatorialproblem. We apply our strategy to get low-degree certificates for Matching, Balanced CSP, TSP, and others.

Two fundamental problems in information integration are data exchange and entity resolution. Data exchange is the task of translating data structured under a source schema into data structured under a target schema. Data exchange is captured by schema mappings that specify the relationship between a source schema and a target schema at a high level. Entity resolution is the task of identifying and linking different representations of the same real-world object. The goal of entity resolution is to create links among existing data. Although schema mapping and entity resolution have been successfully used in many domains, manually designing schema mappings and entity resolution algorithms is a labor-intensive and time-consuming process.In this dissertation, we develop example-driven discovery/learning methods for high-level declarative schema mapping specifications and high-level declarative entity resolution algorithms. This dissertation contains two parts. In Part I, we present our work on extending and refining two major example-driven schema-mapping discovery frameworks, namely, the repair framework introduced by Gottlob and Senellart and the learning framework introduced by ten Cate et al. Gottlob and Senellart introduced a framework for schema-mapping discovery from a single data example, in which the derivation of a schema mapping is cast as an optimization problem. We refine and study this framework in more depth. Among other results, we design a polynomial-time log(n)-approximation algorithm for computing optimal schema mappings from a given set of data examples for a restricted class of schema mappings; moreover, we show that this approximation ratio cannot be improved. We implemented the aforementioned log(n)-approximation algorithm and carried out an experimental evaluation in a real-world mapping scenario. As opposed to the repair framework, in which the schema-mapping discovery problem is cast as an optimization problem, the derivation of a schema mapping is cast as a computational learning problem in the learning framework. We design a learning algorithm that is an Occam algorithm leading up to a PAC learning algorithm for an important class of schema mappings. We also implemented the proposed algorithm and carried out an experimental evaluation using mapping scenarios created by iBench, which is a state-of-the-art benchmarking tool. In Part II, we introduce a new active learning system for entity resolution that learns high-quality entity resolution algorithms. Our focus is on learning entity resolution algorithms in big data scenarios. We implemented the aforementioned active learning system and carried out an experimental evaluation in two real-world big data entity resolution scenarios.

We study a few online and offline facility location and network design problems, including an offline facility location model with submodular opening costs, an online prize-collecting facility location model, an offline singledemand capacitated facility location model and an online prize-collecting Steiner tree problem. In this thesis, we present algorithms for these problems and their approximation ratio or competitive ratio analysis.

Abstract: How to evaluate the performance of an algorithm is a very important subject in computer science, for understanding its applicability, for understanding the problem which it is applied to, and for the development of new ideas that help to improve the existing algorithms. There are two main factors, i.e. the performance measure and the analysis model, that affect the evaluation of an algorithm. In this thesis, we analyse algorithms with approximation ratio as a measure under the worst-case analysis and the smoothed analysis. In particular, several interesting discrete optimization problems from bioinformatics, networking and graph theory are investigated, and currently the best approximation algorithms are designed for them under the classic analysis model — the worst-case analysis and the more ``realistic" model — the smoothed analysis.

This dissertation considers certain graph-theoretic combinatorial problems which have direct application to the efficient computation of derivative matrices (“Jacobians”) which arise in many scientific computing applications. Specifically, we analyze algorithms for Star Bicoloring and establish several analytical results. We establish complexity-theoretic lower bounds on the approximability of algorithms for Star Bicoloring, showing that no such polynomial-time algorithm can achieve an approximation ratio of O(N ^(1/3)-e ) for any e > 0 unless P = NP. We establish the first algorithm (ASBC) for Star Bicoloring with a known approximation upper-bound, showing that ASBC is an O(N ^(2/3 )) polynomial-time approximation algorithm. Based on extension of these results we design a generic framework for greedy Star Bicoloring, and implement several specific methods for comparison. General analysis techniques are developed and applied to both algorithms from the literature (CDC, Hossain and Steihaug, 1998 [1]) as well as those developed as part of the framework. We provide numerous approximability results including the first approximation analysis for the CDC algorithm, showing that CDC is an O(N ^(3/4) ) approximation algorithm. Finally, we observe that all algorithms within this generic framework produce a restricted class of star bicolorings that we refer to as Distance-2 Independent Set Colorings (D2ISC). We establish the relationship between Star Bicoloring and D2ISC. In particular we show that these two notions are not equivalent, that D2ISC is NP-complete and that it cannot be approximated to within O(N ^(1/3 -e) ) for any e > 0 unless P = NP.

Bicycle-sharing systems provide a low-cost, environment-friendly urban transportation option. Efficient management of these systems poses a bicycle rebalancing problem comprising three questions: where do bikes need to be, when must they be there, and how can they get there? I apply operations research techniques to yield practical answers to these questions; my solutions optimize current operations at NYC (Citi)Bike.

Abstract: We study the Single-Minded Pricing, Unique Coverage, and Uniform-Budget Single-Minded Pricing problems on graphs and on geometric objects. In Single Minded Pricing, we are given a set of items and a collection of subsets of the items, called demands. For each demand, we are also given a budget. If the sum of the prices of the items in a demand is less than or equal to the budget of that demand, then the contribution of that demand to the total revenue will be the sum of the prices of the items in that demand and zero otherwise. In this problem, we want to assign prices to the items in order to maximize the total revenue. Uniform-Budget Single-Minded Pricing is a special case of Single-Minded Pricing where the budgets for all the demands are equal. In Unique Coverage, given a set of elements and a collection of subsets of the elements, we want to find a subcollection of the subsets in order to maximize the number of the elements that are uniquely covered. These problems can be studied in different settings, such as on graphs or on geometric objects. When studied on graphs, the items or the elements are the edges of a given graph and the demands or the subsets are paths in the graph, and when studied on geometric objects, the items or the elements are given as points on a two dimensional plane and the demands or the subset as geometric objects on the plane. We introduce approximation algorithms for Single-Minded Pricing, Unique Coverage, and Uniform-Budget Single-Minded Pricing on different geometric objects such as rectangles and squares and on different graphs such as trees. We also prove different hardness results for these problems.

In this dissertation, we focus on solving forest transportation planning related problems, including constraints that consider negative environmental impacts and multi-objective optimizations that provide forest managers and road planers alternatives for making informed decisions. Along this line of study, several multilevel techniques and mataheuristic algorithms have been developed and investigated. The forest transportation planning problem is a fixed-charge problem and known to be NP-hard. The general idea of utilizing multilevel approach is to solve the original problem of which the computational cost maybe prohibitive by using a set of increasingly smaller problems of which the computational cost is cheaper. The multilevel techniques are devised consisting of two parts. The first part is to recursively apply a graph coarsening heuristic to the original problem to produce a set of coarser level problems of which the sizes in terms of number of problem components such as edges and nodes are in decreasing order. The second part is to solve the set of the coarser level problems including the original problem bottom up, starting with the coarsest level. We propose that if coarser level problems inherit important properties (such as attribute value distribution) from their ancestor during the coarsening process, they can be treated as smaller versions of the original problem. Based on this hypothesis, the multilevel techniques use solutions obtained for the coarser level problems to solve the finer level problems. Mainly, we develop multilevel techniques to address three problems, namely a constrained fixed-charge problem, parameter configuration problem, and a multi-objective transportation optimization problem in this study. The performance of the multilevel techniques is compared with other commonly used approaches. The statistical analyses on the experimental results indicate that the multilevel approach can reduce computing time significantly without sacrificing the solution quality.

Spin systems originated in statistical physics as tools for modeling phase transitions in magnets. However, they have since been used to model complex systems arising in several other fields of study (e.g., in Bayesian inference and in the theory of social networks), so that various computational problems associated with them have received much attention in the literature. A lot of progress in the study of these problems has relied upon ideas from statistical physics; one example of this interplay has been the discovery of tight connections between the computational complexity of these problems and the phenomenon of phase transitions that many spin systems exhibit. Conversely, algorithmic ideas have also helped in the study of the phase transition phenomenon.This thesis presents two lines of work that fit into this theme. The first considers the approximation of the partition function, a pivotal quantity associated with spin systems. Here, we obtain—in various settings—deterministic polynomial time algorithms for approximating the partition function in the so called uniqueness regime, and thus strengthen the algorithmic side of the tight correspondence between phase transitions and the computational complexity of the partition function.The second line of work is concerned with the complexity of exact computation of various natural mean observables of spin systems, e.g., the magnetization in the Ising model. We relate these questions to the location of the complex zeros of the partition function, which have been studied in statistical physics because of their connections to the existence of phase transitions, and have been the subject of various celebrated results (such as the Lee–Yang theorem and the Heilmann–Lieb theorem). By proving a novel extension of the Lee–Yang theorem, we show that the magnetization of the ferromagnetic Ising model is indeed as hard to compute as the partition function (i.e., #P–hard). We also obtain similar results for the monomer–dimer model.

As fundamental abstractions of network structures, graphs are everywhere, ranging from biological protein interaction networks and Internet routing networks, to emerging online social networks. Studying graphs is critical to understanding the fundamental processes behind the networks, and of practical importance in experimental research. Although many studies on graphs have been carried out in decades, most of the work focused on small or synthetic graphs. In recent years, because of the unprecedented increase of existing networks and the emergence of new complex networks, more and more big real graphs are becoming available. Compared to the graphs studied in prior work, the graphs from these networks are significantly different in scale, level of dynamics and structure.In this dissertation, we tackle three important graph research problems caused by the significant differences of the big real graphs: efficient node distance computation, graph dynamic analysis and modeling, and graph privacy.First, we target on a fundamental graph analysis problem, i.e. node distance computation. As a primitive of graph analysis and network applications, the computation of shortest path or random walk distances is computationally expensive, and difficult to scale with the sheer size of big real graphs. To address the scalability issue, we design a novel node distance computation method, named graph coordinate systems, to efficiently estimate node distances with high accuracy.Our second work is to understand and model the dynamic processes in big real graphs. Specifically, we propose methods to analyze graph dynamics at multiple network scales and explore temporal properties of network growth. Through measurements on Renren first two-year dynamic data, we find independent and predictable processes at different network levels, and detect self-similar properties in its edge creation process. Based on the observations, we propose a new dynamic graph model to capture both temporal and spatial properties. Calibrated with the Renren dataset, our model successfully produces synthetic graphs showing similar dynamic properties.Finally, to address privacy issue in sharing graphs, we design a graph privacy system to guarantee the required level of privacy. The goal of our work is to design a system that can both maintain a meaningful graph structure and provide strong privacy guarantee. To navigate the tradeoff between the strength of privacy and graph structure utility, we propose a differentially-private graph model. Our rigorous proof shows that the graphs produced by the system can achieve the required level of privacy. By running the system on real graphs collected from Facebook, Internet, and Web, the results demonstrate that the generated synthetic graphs match the original graphs in terms of graph structural metrics and application-level performance.In summary, to analyze and process the graphs from today's large complex networks, we work on three important problems, including efficiently computing node distances in massive graphs, analyzing and modeling high volume of dynamics in big real graphs, and protecting graph privacy in sharing graphs. We propose novel solutions to address these problems. Through our extensive experiments, we show that our designs perform consistently well on big real graphs.

Abstract: In this thesis, we consider min-max vehicle routing problems, specifically min-max tour cover and star cover problems. Given a metric (V,c) and a number k, a set of tours (respectively stars) in G is called a k-tour cover (respectively k-star cover), if they cover all the vertices of G. In the rooted variant, the locations of the roots are given in the input. In Chapter 2, we improve on the approximation ratios of tour cover problems. We present algorithms that improve the approximation ratios of rooted and unrooted min-max k-tour cover problems to (7+epsilon) and (16/3+epsilon) respectively. In Chapter 3, we study the unrooted min-max k-star cover problem and improve the bi-criteria approximation ratio to (O(1/epsilon), 1+epsilon). For the line metric, we present a QPTAS, and in the special case that the stars are non-crossing, we present a PTAS. Then, we show that the problem is APX-hard on the Euclidean metric.

Mechanism design studies optimization problems with inputs from selfishly behaving agents. To a class of relatively simple questions, classical auction theory gives optimal solution which are often too complicated for practical use. This dissertation presents techniques and results on the design and analysis of simple and practical auctions that have provably approximately optimal performances. For single-parameter revenue optimization, we present the k-lookahead auction, which works for coorelated valuation distributions, and we discuss its consequences, which encompass a family of reserveprice-based auctions with approximately optimal revenue. For more general settings, we present the marginal revenue mechanisms as a framework for designing simple mechanisms in very general settings. Both frameworks are motivated with clear economic intuitions. For social welfare maximization in combinatorial auctions, we present an equilibrium analysis for simultaneous item auctions. In particular, we show that when valuations exhibit no complements, the welfare loss in these auctions at Bayesian Nash equilibria is bounded by small constants.

As a fundamental model in Operations Research, polynomial optimization has been receiving increasingly more attention in the recent years, due to its versatile modern applications in engineering such as biomedical engineering, signal processing, material science, speech recognition, and so on. In this thesis, we present a systematic study of polynomial optimization. First, we study the structures of various polynomial functions, based on which efficient algorithms will consequently be developed. The newly developed solution methods will be tested on a variety of engineering applications. Specifically, we first study the class of nonnegative polynomials. Six fundamentally important types of nonnegative quartic functions coagulating into a chain in decreasing order will be presented. This structure is useful in understanding the nature of quartic polynomials. We further consider the polynomial sized representation of a very specific nonnegative polynomial, and this representation enables us to address an open question asserting that the computation of the matrix $2 \mapsto 4$ norm is NP-hard in general. Then we proceed to studying polynomial function in random variables and establish a series of fundamental probability inequalities. Similar to the relationship between the symmetric matrices and the quadratic functions, there also exists a one-to-one correspondence between the super-symmetric tensors and the homogeneous polynomials, and this leads to the knowledge of tensor related problems. We then proceed to a new notion of matrix-rank for the even order tensors. Unlike the CP-rank of tensors, the matrix-rank is easy to compute. On the computational side, the afore-mentioned probability inequalities lead to new approximation algorithms with better approximation ratios than the ones known in the literature. We also propose approximation algorithms for polynomial optimization in complex variables. At the same time, we consider first order algorithms such as the alternating direction method of multipliers (ADMM), and the maximum block improvement algorithms (MBI). Finally, we test the new algorithms by solving real engineering problems including the tensor PCA problem, the tensor recovery problem in computer vision and the radar waveform design problem. Excellent performances of the proposed methods have been confirmed by our numerical results.

We investigate diverse aspects of the performance of wireless networks, including throughput, delay and distributed complexity. One of the main challenges for optimizing them arises from radio interference, an inherent factor in wireless networks.Graph-based interference models represent a large class of interference models widely used for the study of wireless networks,and suffer from the weakness of over-simplifying the interference caused by wireless signals in a local and binary way.A more sophisticated interference model, the physical interference model, based on SINR constraints,is considered more realistic but is more challenging to study (because of its non-linear form and non-local property).In this dissertation, we study the connections between the two types of interference models -- graph-based and physical interference models --and tackle a set of fundamental problems under the physical interference model;previously, some of the problems were still open even under the graph-based interference model, and to those we have provided solutions under both types of interference models.The underlying interference models affect scheduling and power control -- essential building blocks in the operation of wireless networks -- that directly deal with the wireless medium; the physical interference model (compared to graph-based interference model) compounds the problem of efficient scheduling and power control by making it non-local and non-linear.The system performance optimization and tradeoffs with respect to throughput and delay require a ``global\'\' view acrosstransport, network, media access control (MAC), physical layers (referred to as cross-layer optimization)to take advantage of the control planes in different levels of the wireless network protocol stack.This can be achieved by regulating traffic rates, finding traffic flow paths for end-to-end sessions,controlling the access to the wireless medium (or channels),assigning the transmission power, and handling signal reception under interference.The theme of the dissertation isdistributed algorithms and optimization of QoS objectives under the physical interference model.We start by developing the first low-complexity distributed scheduling and power control algorithms for maximizing the efficiency ratio for different interference models;we derive end-to-end per-flow delay upper-bounds for our scheduling algorithms and our delay upper-bounds are the first network-size-independent result known for multihop traffic.Based on that, we design the first cross-layer multi-commodity optimization frameworks for delay-constrained throughput maximization by incorporating the routing and traffic control into the problem scope.Scheduling and power control is also inherent to distributed computing of ``global problems\'\', e.g., the maximum independent set problems in terms of transmitting links and local broadcasts respectively, and the minimum spanning tree problems.Under the physical interference model, we provide the first sub-linear time distributed solutions to the maximum independent set problems, and also solve the minimum spanning tree problems efficiently.We develop new techniques and algorithms and exploit the availability of technologies (full-/half-duplex radios, fixed/software-defined power control) to further improve our algorithms.%This fosters a deeper understanding of distributed scheduling from the network computing point of view.We highlight our main technical contributions, which might be of independent interest to the design and analysis of optimization algorithms.Our techniques involve the use of linear and mixed integer programs in delay-constrained throughput maximization. This demonstrates the combined use of different kinds of combinatorial optimization approaches for multi-criteria optimization.We have developed techniques for queueing analysis under general stochastic traffic to analyze network throughput and delay properties.We use randomized algorithms with rigorously analyzed performance guarantees to overcome the distributed nature of wireless data/control communications.We factor in the availability of emerging radio technologies for performance improvements of our algorithms.Some of our algorithmic techniques that would be of broader use in algorithms for the physical interference model include:formal development of the distributed computing model in the SINR model, and reductions between models of different technological capabilities, the redefinition of interference sets in the setting of SINR constraints, and our techniques for distributed computation of rulings (informally, nodes or links which are well-separated covers).

In this thesis we study the Fault-Tolerant Facility Placement problem (FTFP). In the FTFP problem, we are given a set of sites at which we can open facilities, and a set of clients with demands. To satisfy demands, clients must be connected to open facilities. The goal is to satisfy all clients' demands while minimizing the combined cost of opening facilities and connecting clients to facilities. The problem is NP-hard and hence we study approximation algorithms and their performance guarantees. Approximation algorithms are algorithms that run in polynomial time with provable performance bounds relative to optimal solutions.We present two techniques with which we develop several LP-rounding algorithms with progressively improved approximation ratios. The best ratio we have is 1.575. We also study primal-dual approaches. In particular, we show that a natural greedy algorithm analyzed using the dual-fitting technique gives an approximation ratio of O(log n). On the negative side, under a natural assumption, we give an example showing that the dual-fitting analysis cannot give a ratio better than O(log n / log log n).