Mohit Singh

SODA Conference 2025 Conference Paper

Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees

• Swati Gupta 0001
• Jai Moondra
• Mohit Singh

ICRA Conference 2025 Conference Paper

DeepVL: Dynamics and Inertial Measurements-based Deep Velocity Learning for Underwater Odometry

• Mohit Singh
• Kostas Alexis

This paper presents a learned model to predict the robot-centric velocity of an underwater robot through dynamics-aware proprioception. The method exploits a recurrent neural network using as inputs inertial cues, motor commands, and battery voltage readings alongside the hidden state of the previous time-step to output robust velocity estimates and their associated uncertainty. An ensemble of networks is utilized to enhance the velocity and uncertainty predictions. Fusing the network's outputs into an Extended Kalman Filter, alongside inertial predictions and barometer updates, the method enables long-term underwater odometry without further exteroception. Furthermore, when integrated into visual-inertial odometry, the method assists in enhanced estimation resilience when dealing with an order of magnitude fewer total features tracked (as few as 1) as compared to conventional visual-inertial systems. Tested onboard an underwater robot deployed both in a laboratory pool and the Trondheim Fjord, the method takes less than 5 ms for inference either on the CPU or the GPU of an NVIDIA Orin AGX and demonstrates less than 4% relative position error in novel trajectories during complete visual blackout, and approximately 2% relative error when a maximum of 2 visual features from a monocular camera are available.

ICRA Conference 2024 Conference Paper

An Online Self-calibrating Refractive Camera Model with Application to Underwater Odometry

• Mohit Singh
• Mihir Dharmadhikari
• Kostas Alexis

This work presents a camera model for refractive media such as water and its application in underwater visual-inertial odometry. The model is self-calibrating in real-time and is free of known correspondences or calibration targets. It is separable as a distortion model (dependent on refractive index n and radial pixel coordinate) and a virtual pinhole model (as a function of n). We derive the self-calibration formulation leveraging epipolar constraints to estimate the refractive index and subsequently correct for distortion. Through experimental studies using an underwater robot integrating cameras and inertial sensing, the model is validated regarding the accurate estimation of the refractive index and its benefits for robust odometry estimation in an extended envelope of conditions. Lastly, we show the transition between media and the estimation of the varying refractive index online, thus allowing computer vision tasks across refractive media.

SODA Conference 2024 Conference Paper

Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

• Adam Brown
• Aditi Laddha
• Madhusudhan Reddy Pittu
• Mohit Singh

In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G, and n agents, A, where each agent i ∈ A has a valuation v ij ≥ 0 for each item j ∈ G. In addition, every agent i has a non-negative weight w i such that the weights collectively sum up to 1. The goal is to find an assignment σ: G → A that maximizes. When all the weights equal to, the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present a -approximation algorithm for the weighted Nash Social Welfare problem, where denotes the KL-divergence between the distribution w and the uniform distribution on [ n ]. We generalize the convex programming relaxations for the symmetric variant of Nash Social Welfare presented in [CDG + 17, AGSS17] to two different mathematical programs. The first program is convex and is necessary for computational efficiency, while the second program is a non-convex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and non-convex relaxation.

IROS Conference 2024 Conference Paper

Online Refractive Camera Model Calibration in Visual Inertial Odometry

• Mohit Singh
• Kostas Alexis

This paper presents a general refractive camera model and online co-estimation of odometry and the refractive index of an unknown media. This enables operation in diverse and varying refractive fluids, given only the camera calibration in air. The refractive index is estimated online as a state variable of a monocular visual-inertial odometry framework in an iterative formulation using the proposed camera model. The method was verified on data collected using an underwater robot traversing inside a pool. The evaluations demonstrate convergence to the ideal refractive index for water despite significant perturbations in the initialization. Simultaneously, the approach enables on-par visual-inertial odometry performance in refractive media without prior knowledge of the refractive index or requirement of medium-specific camera calibration.

FOCS Conference 2022 Conference Paper

Determinant Maximization via Matroid Intersection Algorithms

• Adam Brown
• Aditi Laddha
• Madhusudhan Reddy Pittu
• Mohit Singh
• Prasad Tetali

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [1], convex geometry [2], fair allocations [3], combinatorics [4], spectral graph theory [5], network design, and random processes [6]. In an instance of a determinant maximization problem, we are given a collection of vectors $U=\{v_{1}, \cdots, \ v_{n}\}\subset \mathbb{R}^{d}$, and a goal is to pick a subset $S\subseteq U$ of given vectors to maximize the determinant of the matrix $\displaystyle \sum_{i\in S}v_{i}v_{i}^{\text{T}}$. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint $(|S|\leq k)$ or matroid constraint $(S$ is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a $r^{O(r)}$-approximation for any matroid of rank $r \leq d$. This improves previous results that give $e^{O(r^{2})}$-approximation algorithms relying on $e^{O(r)}$-approximate estimation algorithms [4], [7] –[9] for any r$\leq$d. All previous results use convex relaxations and their relationship to stable polynomials and strongly $\log$-concave polynomials or non-convex relaxations for the problem [10]. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the $\det(.)$ function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

IROS Conference 2021 Conference Paper

A Highly Maneuverable Hybrid Energy-Efficient Rolling/Flying System

• Sahand Sabet
• Mohit Singh
• Mohammad Poursina
• Parviz E. Nikravesh

Spherical robots are typically comprised of an actuation unit enclosed by a spherical shell. Among nonholonomic systems, spherical robots offer the best maneuverability and lowest energy consumption (due to their omnidirectional movement and single contact point with the ground). This allows them to traverse rough and uneven terrains. Further, using their ability to roll on the ground, they can provide a significantly higher operating time compared to aerial-only robots. Unfortunately, these robots are under-emphasized by researchers compared to other robots (i. e. , legged or wheeled robots). Additionally, despite their potential to be used in a multitude of real-world applications, spherical robots have not been successfully adopted by the industry. This is due to the lack of controllability and traversability of the developed designs. In this paper, we introduce a hybrid rolling/flying robot. This design benefits from a flywheel to reduce the effects of the terrain (shocks and vibrations) on the camera and sensors. Our design allows the application of existing control algorithms of drones (such as PX4) on a rolling system. In addition, we propose a dynamics model that can use the point cloud representation of the terrain to simulate the motion of the system with applications in real-time modeling and control.

FOCS Conference 2020 Conference Paper

Maximizing Determinants under Matroid Constraints

• Vivek Madan
• Aleksandar Nikolov
• Mohit Singh
• Uthaipon Tao Tantipongpipat

Given a set of vectors $\mathbf{v}_{1}, \ldots, \mathbf{v}_{n}\in \mathbb{R}^{d}$ and a matroid $\mathcal{M}=([n], \mathcal{I})$, we study the problem of finding a basis $S$ of $\mathcal{M}$ such that $\det(\sum\nolimits_{i\in S}\mathbf{v}_{i}\mathbf{v}_{i}^{\top})$ is maximized. This problem appears in a diverse set of areas, such as experimental design, fair allocation of goods, network design, and machine learning. The current best results include an $e^{2k}$ -estimation for any matroid of rank $k$ [8] and a $(1+\epsilon)^{d}$ -approximation for a uniform matroid of rank $k \geq d+\frac{d}{\epsilon}$ [30], where the rank $k\geq d$ denotes the desired size of the optimal set. Our main result is a new approximation algorithm for the general problem with an approximation guarantee that depends only on the dimension $d$ of the vectors, and not on the size $k$ of the output set. In particular, we show an $(O(d))^{d}$ -estimation and an $(O(d))^{d^{3}}$ -approximation for any matroid, giving a significant improvement over prior work when $k\gg d$. Our result relies on showing that there exists an optimal solution to a convex programming relaxation for the problem which has sparse support; in particular, no more than $O(d^{2})$ variables of the solution have fractional values. The sparsity results rely on the interplay between the first order optimality conditions for the convex program and matroid theory. We believe that the techniques introduced to show sparsity of optimal solutions to convex programs will be of independent interest. We also give a new randomized rounding algorithm that crucially exploits the sparsity of solutions to the convex program. To show the approximation guarantee, we utilize recent works on strongly log-concave polynomials [8], [4] and show new relationships between different convex programs [33], [6] studied for the problem. Finally, we show how to use the estimation algorithm to give an efficient deterministic approximation algorithm. Once again, the algorithm crucially relies on sparsity of the fractional solution to guarantee that the approximation factor depends solely on the dimension $d$.

ICML Conference 2020 Conference Paper

On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness

• Sebastian Pokutta
• Mohit Singh
• Alfredo Torrico

It is well known that the standard greedy algorithm guarantees a worst-case approximation factor of $1-1/e$ when maximizing a monotone submodular function under a cardinality constraint. However, empirical studies show that its performance is substantially better in practice. This raises a natural question of explaining this improved performance of the greedy algorithm. In this work, we define sharpness for submodular functions as a candidate explanation for this phenomenon. We show that the greedy algorithm provably performs better as the sharpness of the submodular function increases. This improvement ties in closely with the faster convergence rates of first order methods for sharp functions in convex optimization.

SODA Conference 2020 Conference Paper

Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems

• Sepehr Abbasi Zadeh
• Nikhil Bansal 0001
• Guru Guruganesh
• Aleksandar Nikolov
• Roy Schwartz 0002
• Mohit Singh

Semi-definite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson [23] has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, e. g. , M ax -C ut, for many others, e. g. , M ax -SAT and M ax -D i C ut, the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semi-definite relaxations are known. In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including M ax -C ut, M ax -2SAT, and M ax -D i C ut, and derive new algorithms that are competitive with the best known results. To illustrate the versatility and general applicability of our approach, we give new approximation algorithms for the M ax -C ut problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations.

NeurIPS Conference 2019 Conference Paper

Multi-Criteria Dimensionality Reduction with Applications to Fairness

• Uthaipon Tantipongpipat
• Samira Samadi
• Mohit Singh
• Jamie Morgenstern
• Santosh Vempala

Dimensionality reduction is a classical technique widely used for data analysis. One foundational instantiation is Principal Component Analysis (PCA), which minimizes the average reconstruction error. In this paper, we introduce the multi-criteria dimensionality reduction problem where we are given multiple objectives that need to be optimized simultaneously. As an application, our model captures several fairness criteria for dimensionality reduction such as the Fair-PCA problem introduced by Samadi et al. [NeurIPS18] and the Nash Social Welfare (NSW) problem. In the Fair-PCA problem, the input data is divided into k groups, and the goal is to find a single d-dimensional representation for all groups for which the maximum reconstruction error of any one group is minimized. In NSW the goal is to maximize the product of the individual variances of the groups achieved by the common low-dimensinal space. Our main result is an exact polynomial-time algorithm for the two-criteria dimensionality reduction problem when the two criteria are increasing concave functions. As an application of this result, we obtain a polynomial time algorithm for Fair-PCA for k=2 groups, resolving an open problem of Samadi et al. [NeurIPS18], and a polynomial time algorithm for NSW objective for k=2 groups. We also give approximation algorithms for k>2. Our technical contribution in the above results is to prove new low-rank properties of extreme point solutions to semi-definite programs. We conclude with the results of several experiments indicating improved performance and generalized application of our algorithm on real-world datasets.

SODA Conference 2019 Conference Paper

Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design

• Aleksandar Nikolov
• Mohit Singh
• Uthaipon Tao Tantipongpipat

We study the A -optimal design problem where we are given vectors υ 1, …, υ n ∊ ℝ d, an integer k ≥ d, and the goal is to select a set S of k vectors that minimizes the trace of (∑ i ∊ S v i v i ⊺ ) −1. Traditionally, the problem is an instance of optimal design of experiments in statistics [35] where each vector corresponds to a linear measurement of an unknown vector and the goal is to pick k of them that minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placement in wireless networks [22], sparse least squares regression [8], feature selection for k -means clustering [9], and matrix approximation [13, 14, 5]. In this paper, we introduce proportional volume sampling to obtain improved approximation algorithms for A -optimal design. Given a matrix, proportional volume sampling involves picking a set of columns S of size k with probability proportional to µ ( S ) times det(∑ i ∊ S v i v i ⊺ ) for some measure µ. Our main result is to show the approximability of the A -optimal design problem can be reduced to approximate independence properties of the measure µ. We appeal to hardcore distributions as candidate distributions µ that allow us to obtain improved approximation algorithms for the A -optimal design. Our results include a d -approximation when k = d, an (1 + ∊ )-approximation when and -approximation when repetitions of vectors are allowed in the solution. We also consider generalization of the problem for k ≤ d and obtain a k -approximation. We also show that the proportional volume sampling algorithm gives approximation algorithms for other optimal design objectives (such as D -optimal design [36] and generalized ratio objective [27]) matching or improving previous best known results. Interestingly, we show that a similar guarantee cannot be obtained for the E -optimal design problem. We also show that the A -optimal design problem is NP-hard to approximate within a fixed constant when k = d.

SODA Conference 2018 Conference Paper

Approximate Positive Correlated Distributions and Approximation Algorithms for D-optimal Design

• Mohit Singh
• Weijun Xie 0001

Experimental design is a classical area in statistics [21] and has also found new applications in machine learning[2]. In the combinatorial experimental design problem, the aim is to estimate an unknown m -dimensional vector x from linear measurements where a Gaussian noise is introduced in each measurement. The goal is to pick k out of the given n experiments so as to make the most accurate estimate of the unknown parameter x. Given a set S of chosen experiments, the most likelihood estimate x ′ can be obtained by a least squares computation. One of the robust measures of error estimation is the D -optimality criterion [27] which aims to minimize the generalized variance of the estimator. This corresponds to minimizing the volume of the standard confidence ellipsoid for the estimation error x – x ′. The problem gives rise to two natural variants depending on whether repetitions of experiments is allowed or not. The latter variant, while being more general, has also found applications in geographical location of sensors [19]. We show a close connection between approximation algorithms for the D-optimal design problem and constructions of approximately m-wise positively correlated distributions. This connection allows us to obtain a approximation for the D -optimal design problem with and without repetitions giving the first constant factor approximation for the problem. We then consider the case when the number of experiments chosen is much larger than the dimension m and show one can obtain (1 – ∊ )-approximation if when repetitions are allowed and if when no repetitions are allowed improving on previous work.

NeurIPS Conference 2018 Conference Paper

The Price of Fair PCA: One Extra dimension

• Samira Samadi
• Uthaipon Tantipongpipat
• Jamie Morgenstern
• Mohit Singh
• Santosh Vempala

We investigate whether the standard dimensionality reduction technique of PCA inadvertently produces data representations with different fidelity for two different populations. We show on several real-world data sets, PCA has higher reconstruction error on population A than on B (for example, women versus men or lower- versus higher-educated individuals). This can happen even when the data set has a similar number of samples from A and B. This motivates our study of dimensionality reduction techniques which maintain similar fidelity for A and B. We define the notion of Fair PCA and give a polynomial-time algorithm for finding a low dimensional representation of the data which is nearly-optimal with respect to this measure. Finally, we show on real-world data sets that our algorithm can be used to efficiently generate a fair low dimensional representation of the data.

STOC Conference 2016 Conference Paper

Maximizing determinants under partition constraints

• Aleksandar Nikolov
• Mohit Singh

Given a positive semidefinte matrix L whose columns and rows are indexed by a set U , and a partition matroid M =( U , I ), we study the problem of selecting a basis B of M such that the determinant of the submatrix of L induced by the rows and columns in B is maximized. This problem appears in many areas including determinantal point processes in machine learning, experimental design, geographical placement problems, discrepancy theory and computational geometry to model subset selection problems that incorporate diversity.

SODA Conference 2014 Conference Paper

Approximating Minimum Cost Connectivity Orientation and Augmentation

• Mohit Singh
• László A. Végh

STOC Conference 2014 Conference Paper

Entropy, optimization and counting

• Mohit Singh
• Nisheeth K. Vishnoi

We study the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. There has been a tremendous amount of interest in such distributions due to their applicability in areas such as statistical physics, economics, biology, information theory, machine learning, combinatorics and algorithms. However, a rigorous and systematic study of how to compute such distributions has been lacking. Since the underlying set of discrete objects can be exponential in the input size, the first question in such a study is if max-entropy distributions have polynomially-sized descriptions. We start by giving a structural result which shows that such succinct descriptions exist under very general conditions. Subsequently, we use techniques from convex programming to give a meta-algorithm that can efficiently (approximately) compute max-entropy distributions provided one can efficiently (approximately) count the underlying discrete set . Thus, we can translate a host of existing counting algorithms, developed in an unrelated context, into algorithms that compute max-entropy distributions. Conversely, we prove that counting oracles are necessary for computing max-entropy distributions: we show how algorithms that compute max-entropy distributions can be converted into counting algorithms.

FOCS Conference 2014 Conference Paper

LP-Based Algorithms for Capacitated Facility Location

• Hyung-Chan An
• Mohit Singh
• Ola Svensson

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no linear programming relaxation was known to efficiently approximate the problem. In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. We demonstrate that the fundamental theories of multi-commodity flows and matchings provide key insights that lead to the strong relaxation. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.

FOCS Conference 2011 Conference Paper

A Randomized Rounding Approach to the Traveling Salesman Problem

• Shayan Oveis Gharan
• Amin Saberi
• Mohit Singh

For some positive constant ϵ 0, we give a (3/2-ϵ 0 )-approximation algorithm for the following problem: given a graph G 0 = (V, V 0 ), find the shortest tour that visits every vertex at least once. This is a special case of the metric traveling salesman problem when the underlying metric is defined by shortest path distances in Go. The result improves on the 3/2-approximation algorithm due to Christofides [13] for this special case. Similar to Christofides, our algorithm finds a spanning tree whose cost is upper bounded by the optimum, then it finds the minimum cost Eulerian augmentation (or T-join) of that tree. The main difference is in the selection of the spanning tree. Except in certain cases where the solution of LP is nearly integral, we select the spanning tree randomly by sampling from a maximum entropy distribution defined by the linear programming relaxation. Despite the simplicity of the algorithm, the analysis builds on a variety of ideas such as properties of strongly Rayleigh measures from probability theory, graph theoretical results on the structure of near minimum cuts, and the integrality of the T-join polytope from polyhedral theory. Also, as a byproduct of our result, we show new properties of the near minimum cuts of any graph, which may be of independent interest.

FOCS Conference 2011 Conference Paper

Online Node-Weighted Steiner Tree and Related Problems

• Joseph Naor
• Debmalya Panigrahi
• Mohit Singh

We obtain the first online algorithms for the node-weighted Steiner tree, Steiner forest and group Steiner tree problems that achieve a poly-logarithmic competitive ratio. Our algorithm for the Steiner tree problem runs in polynomial time, while those for the other two problems take quasi-polynomial time. Our algorithms can be viewed as online LP rounding algorithms in the framework of Buchbinder and Naor (Foundations and Trends in Theoretical Computer Science, 2009); however, while the natural LP formulation of these problems do lead to fractional algorithms with a poly-logarithmic competitive ratio, we are unable to round these LPs online without losing a polynomial factor. Therefore, we design new LP formulations for these problems drawing on a combination of paradigms such as spider decompositions, low-depth Steiner trees, generalized group Steiner problems, etc. and use the additional structure provided by these to round the more sophisticated LPs losing only a poly-logarithmic factor in the competitive ratio. As further applications of our techniques, we also design polynomial-time online algorithms with poly-logarithmic competitive ratios for two fundamental network design problems in edge-weighted graphs: the group Steiner forest problem (thereby resolving an open question raised by Chekuri et. al. (SODA 2008)) and the single source ℓ-vertex connectivity problem (which complements similar results for the corresponding edge-connectivity problem due to Gupta et. al. (STOC 2009)).

STOC Conference 2008 Conference Paper

Additive approximation for bounded degree survivable network design

• Lap Chi Lau
• Mohit Singh

We study a general network design problem with additional degree constraints. Given connectivity requirements r uv for all pairs of vertices, a Steiner network is a graph in which there are at least r uv edge-disjoint paths between u and v for all pairs of vertices u,v . In the MINIMUM BOUNDED-DEGREE STEINER NETWORK problem, we are given an undirected graph G with an edge cost for each edge, a connectivity requirement r uv for each pair of vertices u and v , and a degree upper bound for each vertex v . The task is to find a minimum cost Steiner network which satisfies all the degree upper bounds. The aim of this paper is to design approximation algorithms that minimize the total cost and the degree violation simultaneously. Our main results are the following: There is a polynomial time algorithm which returns a Steiner forest of cost at most 2 OPT and the degree violation at each vertex is at most 3,where OPT is the cost of an optimal solution which satisfies all the degree bounds. There is a polynomial time algorithm which returns a Steiner network of cost at most 2 OPT and the degree violation at each vertex is at most 6 r max +3,where OPT is the cost of an optimal solution which satisfies all the degree bounds, and r max := max u,v { r uv }. These results achieve the best known guarantees for both the total cost and the degree violation simultaneously. As corollaries, these results provide the first additive approximation algorithms for finding low degree subgraphs including Steiner forests, k -edge-connected subgraphs, and Steiner networks. The algorithms develop on the iterative relaxation method applied to a natural linear programming relaxation as in [10, 16, 22]. The new algorithms avoid paying a multiplicative factor of two on the degree bounds even though the algorithm can only pick edges with fractional value 1/2 . This is based on a stronger characterization of the basic so-algorithm is nearly tight.

FOCS Conference 2008 Conference Paper

Set Covering with our Eyes Closed

• Fabrizio Grandoni 0001
• Anupam Gupta 0001
• Stefano Leonardi 0001
• Pauli Miettinen
• Piotr Sankowski
• Mohit Singh

Given a universe U of n elements and a weighted collection l of m subsets of U, the universal set cover problem is to a-priori map each element u epsi U to a set S(u) epsi l containing u, so that X sube U is covered by S(X)=U uepsiX S(u). The aim is finding a mapping such that the cost of S(X) is as close as possible to the optimal set-cover cost for X. (Such problems are also called oblivious or a-priori optimization problems.) Unfortunately, for every universal mapping, the cost of S(X) can be Omega(radicn) times larger than optimal if the set X is adversarially chosen. In this paper we study the performance on average, when X is a set of randomly chosen elements from the universe: we show how to efficiently find a universal map whose expected cost is O(log mn) times the expected optimal cost. In fact, we give a slightly improved analysis and show that this is the best possible. We generalize these ideas to weighted set cover and show similar guarantees to (non-metric) facility location, where we have to balance the facility opening cost with the cost of connecting clients to the facilities. We show applications of our results to universal multi-cut and disc-covering problems, and show how all these universal mappings give us stochastic online algorithms with the same competitive factors.

STOC Conference 2007 Conference Paper

Approximating minimum bounded degree spanning trees to within one of optimal

• Mohit Singh
• Lap Chi Lau

In the Minimum Bounded Degree Spanning Tree problem, we aregiven an undirected graph with a degree upper bound B v on eachvertex v, and the task is to find a spanning tree of minimumcost which satisfies all the degree bounds. Let OPT be the costof an optimal solution to this problem. In this paper, we presenta polynomial time algorithm which returns a spanning tree T ofcost at most OPT and d T (v) ≤ B v +1 for all v, where d T (v) denotes the degree of v in T. This generalizes aresult of Furer and Raghavachari [8] to weighted graphs, andsettles a 15-year-old conjecture of Goemans [10] affirmatively. The algorithm generalizes when each vertex v hasa degree lower bound A v and a degree upper bound B v , andreturns a spanning tree with cost at most OPT and A v - 1 ≤d T (v) ≤ B v + 1 for all v. This is essentially the bestpossible. The main technique used is an extension of the iterativerounding method introduced by Jain [12] for the design ofapproximation algorithms.

STOC Conference 2007 Conference Paper

Survivable network design with degree or order constraints

• Lap Chi Lau
• Joseph Naor
• Mohammad R. Salavatipour
• Mohit Singh

SODA Conference 2006 Conference Paper

Approximating the k -multicut problem

• Daniel Golovin
• Viswanath Nagarajan
• Mohit Singh

FOCS Conference 2005 Conference Paper

How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems

• Kedar Dhamdhere
• Vineet Goyal
• R. Ravi 0001
• Mohit Singh

Robust optimization has traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worst-case among the various uncertain scenarios in the model. While these approaches may be thought of defining data- or cost-robust problems, we formulate a new "demand-robust" model motivated by recent work on two-stage stochastic optimization problems. We propose this in the framework of general covering problems and prove a general structural lemma about special types of first-stage solutions for such problems: there exists a first-stage solution that is a minimal feasible solution for the union of the demands for some subset of the scenarios and its objective function value is no more than twice the optimal. We then provide approximation algorithms for a variety of standard discrete covering problems in this setting, including minimum cut, minimum multi-cut, shortest paths, Steiner trees, vertex cover and un-capacitated facility location. While many of our results draw from rounding approaches recently developed for stochastic programming problems, we also show new applications of old metric rounding techniques for cut problems in this demand-robust setting.