We study the problem of maximizing a monotone submodular function subject to a matroid independence constraint. For more than a decade, a rich body of work has studied this problem. Initially, a tight approximation of (1−1e) was given using the continuous greedy algorithm [Calinescu-Chekuri-Pal-Vondrák STOC‘2008] and later non-oblivious local search techniques were able to match this tight approximation guarantee [Filmus-Ward FOCS‘2012] and [Buchbinder-Feldman FOCS‘2024].

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.

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.

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.

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 vij ≥ 0 for each item j ∈ G. In addition, every agent i has a non-negative weight wi 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 consider the Max--Section problem, where we are given an undirected graph G=(V,E)equipped with non-negative edge weights w: E → R_+ and the goal is to find a partition of V into three equisized parts while maximizing the total weight of edges crossing between different parts. Max-3-Section is closely related to other well-studied graph partitioning problems, e.g., Max-Cut, Max-3-Cut, and Max-Bisection. We present a polynomial time algorithm achieving an approximation of 0.795, that improves upon the previous best known approximation of 0.673. The requirement of multiple parts that have equal sizes renders Max-3-Section much harder to cope with compared to, e.g., Max-Bisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result.

Given a set of facilities and clients, and costs to open facilities, the classic facility location problem seeks to open a set of facilities and assign each client to one open facility to minimize the cost of opening the chosen facilities and the total distance of the clients to their assigned open facilities. Such an objective may induce an unequal cost over certain socioeconomic groups of clients (i.e., total distance traveled by clients in such a group). This is important when planning the location of socially relevant facilities such as emergency rooms.

We study the capacity planning and allocation decisions for multiple heterogeneous resources, considering potential demand scenarios, where each demand requests a subset of the available resource types simultaneously at a specified time, location, and duration (smRmD). We model this problem as a two-stage stochastic integer program and consider two variants for the objective function: (a) maximize the expected reward of demands met over all scenarios, subject to a budget B for resources, and (b) maximize the expected reward of demands met over all scenarios minus the cost of resources. Contributions of this work include (i) a thorough complexity analysis of smRmD and its variants, (ii) analysis of structural properties, (iii) development of various approximation algorithms using the unique structural properties of smRmD and its variants, and (iv) an extensive computational study to explore the ease with which exact and approximate solutions may be found. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This research has been supported in part by National Science Foundation (NSF) Graduate Research Fellowship [DGE-1650044], NSF [Grants CMMI-1538860, NSF-AF:1910423, and NSF-AF:1717947], and the following Georgia Tech benefactors: William W. George, Andrea Laliberte, Richard ”Rick” E. & Charlene Zalesky, and Claudia & Paul Raines.

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.

We consider the problem of allocating multiple heterogeneous resources geographically and over time to meet demands that require some subset of the available resource types simultaneously at a specified time, location, and duration. The objective is to maximize the total reward accrued from meeting (a subset of) demands. We model this problem as an integer program, show that it is NP-hard, and analyze the complexity of various special cases. We introduce approximation algorithms and an extension to our problem that considers travel costs. Finally, we test the performance of the integer programming model in an extensive computational study.

This issue of SICOMP contains ten specially selected papers from STOC 2017, the Forty-ninth Annual ACM Symposium on the Theory of Computing, which was held June 19--23 in Montreal, Canada. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough reviewing process of SICOMP. The program committee for STOC 2017 consisted of Nina Balcan, Allan Borodin, Keren Censor-Hillel, Edith Cohen, Artur Czumaj, Yevgeniy Dodis, Andrew Drucker, Nick Harvey, Monika Henzinger, Russell Impagliazzo, Ken-ichi Kawarabayashi, Ravi Kumar, James R. Lee, Katrina Ligett, Aleksander Mądry, Cristopher Moore, Jelani Nelson, Eric Price, Amit Sahai, Jared Saia, Shubhangi Saraf, Alexander Sherstov, Mohit Singh, and Gábor Tardos. The program chair was Valerie King. Included in this issue are the following papers: ``Short Presburger Arithmetic Is Hard," by Danny Nguyen and Igor Pak, proves that the satisfiability of short sentences in Presburger arithmetic with $m+2$ alternating quantifiers is $\Sigma^{{P}}_m$-complete or $\Pi^{{P}}_m$-complete when the first quantifier is $\exists$ or $\forall$, respectively. ``An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy," by Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma, gets an explicit bipartite Ramsey graph (or a twosource extractor) for sets of size 2$k$ for $k = O(\log n \log \log n)$, using the currently best explicit nonmalleable extractors. ``Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain," by Jin-Yi Cai and Zhiguo Fu, classifies all counting CSPs over Boolean variables into one of three categories: polynomial-time tractable, \#P-hard for general instances but solvable in polynomial time over planar graphs, and \#P-hard over planar graphs. ``Deciding Parity Games in Quasipolynomial Time," by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan, shows the parameterized parity game, with $n$ nodes and $m$ priorities, is in the class of fixed parameter tractable problems when parameterized over $m$. ``New Hardness Results for Routing on Disjoint Paths," by Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat, proves that node-disjoint paths is $2^{\Omega(\sqrt{\log n})}$-hard to approximate, unless all problems in NP have algorithms with running time $n^{O(\log n)}$. ``A Weighted Linear Matroid Parity Algorithm," by Satoru Iwata and Yusuke Kobayashi, presents a combinatorial, deterministic, strongly polynomial-time algorithm for the weighted linear matroid parity problem. ``Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace," by William M. Hoza and Chris Umans, shows that $\mathbf{BPL} \subseteq \bigcap_{\alpha > 0} {DSPACE}(\log^{1 + \alpha} n)$, assuming that for every derandomization result for log-space algorithms there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. ``Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs," by Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra, shows that for CSPs, subexponential size LP relaxations are as powerful as $n^{\Omega(1)}$-rounds of the Sherali--Adams LP hierarchy. ``Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model," by Ran Canetti, Oxana Poburinnaya, and Muthuramakrishnan Venkitasubramaniam, defines a new type of encryption and shows that Yao's garbling scheme, implemented with this encryption mechanism, is secure against adaptive adversaries. ``Geodesic Walks in Polytopes," by Yin Tat Lee and Santosh Vempala, introduces the geodesic walk for sampling Riemannian manifolds and applies it to the problem of generating uniform random points from the interior of polytopes in ${\mathbb{R}}^{n}$ specified by m inequalities; the resulting sampling algorithm for polytopes mixes in $O^{*}(mn^{\frac{3}{4}})$ steps. We thank the authors, the STOC 2017 program committee, the STOC 2017 external reviewers, and the SICOMP referees for all of their hard work. Andy Drucker, Ravi Kumar, Amit Sahai, Mohit Singh, Guest editors

Semidefinite 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 [ 31 ] 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., Max-Cut , for many others, e.g., Max-SAT and Max-DiCut , 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 Max-Cut , Max-2SAT , and Max-DiCut , 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 Max-Cut problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations.

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.

Constrained submodular function maximization has been used in subset selection problems such as selection of most informative sensor locations. Although these models have been quite popular, the solutions obtained via this approach are unstable to perturbations in data defining the submodular functions. Robust submodular maximization has been proposed as a richer model that aims to overcome this discrepancy as well as increase the modeling scope of submodular optimization. In this work, we consider robust submodular maximization with structured combinatorial constraints and give efficient algorithms with provable guarantees. Our approach is applicable to constraints defined by single or multiple matroids and knapsack as well as distributionally robust criteria. We consider both the offline setting where the data defining the problem are known in advance and the online setting where the input data are revealed over time. For the offline setting, we give a general (nearly) optimal bicriteria approximation algorithm that relies on new extensions of classical algorithms for submodular maximization. For the online version of the problem, we give an algorithm that returns a bicriteria solution with sublinear regret. Summary of Contribution: Constrained submodular maximization is one of the core areas in combinatorial optimization with a wide variety of applications in operations research and computer science. Over the last decades, both communities have been interested on the design and analysis of new algorithms with provable guarantees. Sensor location, influence maximization and data summarization are some of the applications of submodular optimization that lie at the intersection of the aforementioned communities. Particularly, our work focuses on optimizing several submodular functions simultaneously. We provide new insights and algorithms to the offline and online variants of the problem which significantly expand the related literature. At the same time, we provide a computational study that supports our theoretical results.

Given a set of vectors v1, ... , vn∈ Rdand a matroid M=([n],I), we study the problem of finding a basis S of M such that det(Σi∈sviviT) 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 e2k-estimation for any matroid of rank k [8] and a (1+ε)d-approximation for a uniform matroid of rank k ≥ d+[d/(ε)] [30], where the rank k ≥ 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))d3-approximation for any matroid, giving a significant improvement over prior work when k ≫ 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(d2) 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.

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.

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., Max-Cut, for many others, e.g., Max-SAT and Max-DiCut, 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 Max-Cut, Max-2SAT, and Max-DiCut, 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 Max-Cut problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations.

Musculoskeletal (MSK) ultrasound imaging aims to provide pictures of tissues and bones such as muscles, tendons, ligaments, joints and soft tissues throughout the body. One of the major landmarks in MSK ultrasound are the bones, and segmentation of bone surface has numerous applications in computer-aided orthopedic diagnosis. In this work, a novel method of bone aware image enhancement of MSK ultrasound images is presented. A combination of fundamental and harmonic US images is used for bone segmentation. The method for bone segmentation takes into account the acoustic characteristics of the intensity of bones used for computing their acoustic shadows, local phase-based features such as local energy, local phase, and feature symmetry based on a reported work in literature. It is combined with integrated backscattering of the bone to provide a probability map of the bone. Bone location in probability map was found based on the centroid of the intensity distribution. Further, image enhancement of the extracted region of interest based on the bone for distinctive visualization of the muscular and tendon region above the bone structure is presented. The image enhancement techniques employed are gamma correction, histogram equalization, adaptive histogram equalization and an improved frequency based super-resolution of ultrasound images.

Constrained submodular function maximization has been used in subset selection problems such as selection of most informative sensor locations. While these models have been quite popular, the solutions obtained via this approach are unstable to perturbations in data defining the submodular functions. Robust submodular maximization has been proposed as a richer model that aims to overcome this discrepancy as well as increase the modeling scope of submodular optimization. In this work, we consider robust submodular maximization with structured combinatorial constraints and give efficient algorithms with provable guarantees. Our approach is applicable to constraints defined by single or multiple matroids, knapsack as well as distributionally robust criteria. We consider both the offline setting where the data defining the problem is known in advance as well as the online setting where the input data is revealed over time. For the offline setting, we give a nearly optimal bi-criteria approximation algorithm that relies on new extensions of the classical greedy algorithm. For the online version of the problem, we give an algorithm that returns a bi-criteria solution with sub-linear regret.

In an optimal design problem, we are given a set of linear experiments $v_1,…,v_n\in \mathbb{R}^d$ and $k \geq d$, and our goal is to select a set or a multiset $S \subseteq [n]$ of size $k$ such that $\Phi((\sum_{i \in S} v_i v_i^\top )^{-1})$ is minimized. When $\Phi(M) = Determinant(M)^{1/d}$, the problem is known as the D-optimal design problem, and when $\Phi(M) = Trace(M)$, it is known as the A-optimal design problem. One of the most common heuristics used in practice to solve these problems is the local search heuristic, also known as the Fedorov’s exchange method (Fedorov, 1972). This is due to its simplicity and its empirical performance (Cook and Nachtrheim, 1980; Miller and Nguyen, 1994; Atkinson et al., 2007). However, despite its wide usage no theoretical bound has been proven for this algorithm. In this paper, we bridge this gap and prove approximation guarantees for the local search algorithms for D-optimal design and A-optimal design problems. We show that the local search algorithms are asymptotically optimal when $\frac{k}{d}$ is large. In addition to this, we also prove similar approximation guarantees for the greedy algorithms for D-optimal design and A-optimal design problems when $\frac{k}{d}$ is large.

Motivated by the use of high speed circuit switches in large scale data centers, we consider the problem of circuit switch scheduling. In this problem we are given demands between pairs of servers and the goal is to schedule at every time step a matching between the servers while maximizing the total satisfied demand over time. The crux of this scheduling problem is that once one shifts from one matching to a different one a fixed delay delta is incurred during which no data can be transmitted. For the offline version of the problem we present a (1-(1/e)-epsilon) approximation ratio (for any constant epsilon >0). Since the natural linear programming relaxation for the problem has an unbounded integrality gap, we adopt a hybrid approach that combines the combinatorial greedy with randomized rounding of a different suitable linear program. For the online version of the problem we present a (bi-criteria) ((e-1)/(2e-1)-epsilon)-competitive ratio (for any constant epsilon >0 ) that exceeds time by an additive factor of O(delta/epsilon). We note that no uni-criteria online algorithm is possible. Surprisingly, we obtain the result by reducing the online version to the offline one.

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.

We present a spectral approach to design approximation algorithms for network design problems. We observe that the underlying mathematical questions are the spectral rounding problems, which were studied in spectral sparsification and in discrepancy theory. We extend these results to incorporate additional nonnegative linear constraints, and show that they can be used to significantly extend the scope of network design problems that can be solved. Our algorithm for spectral rounding is an iterative randomized rounding algorithm based on the regret minimization framework. In some settings, this provides an alternative spectral algorithm to achieve constant factor approximation for the classical survivable network design problem, and partially answers a question of Bansal about survivable network design with concentration property. We also show many other applications of the spectral rounding results, including weighted experimental design and spectral network design.

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.

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.

We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial-time 6-approximation algorithm for finding a minimum cost subgraph of an undirected graph $G$ that admits an orientation covering a nonnegative crossing $G$-supermodular demand function, as defined by Frank [ J. Comb. Theory Ser. B, 28 (1980), pp. 251--261]. An important example is $(k,\ell)$-edge-connectivity, a common generalization of global and rooted edge-connectivity. Our algorithm is based on a nonstandard application of the iterative rounding method. We observe that the standard linear program with cut constraints is not amenable and use an alternative linear program with partition and copartition constraints instead. The proof requires a new type of uncrossing technique on partitions and copartitions. We also consider the problem setting when the cost of an edge can be different for the two possible orientations. The problem becomes substantially more difficult already for the simpler requirement of $k$-edge-connectivity. Khanna, Naor, and Shepherd [ SIAM J. Discrete Math., 19 (2005), pp. 245--257] showed that the integrality gap of the natural linear program is at most $4$ when $k=1$ and conjectured that it is constant for all fixed $k$. We disprove this conjecture by showing an $\Omega(|V|)$ integrality gap even when $k=2$.

We study the problem of allocating m items to n agents subject to maximizing the Nash social welfare (NSW) objective. We write a novel convex programming relaxation for this problem, and we show that a simple randomized rounding algorithm gives a 1/e approximation factor of the objective, breaking the 1/2e^(1/e) approximation factor of Cole and Gkatzelis. Our main technical contribution is an extension of Gurvits's lower bound on the coefficient of the square-free monomial of a degree m-homogeneous stable polynomial on m variables to all homogeneous polynomials. We use this extension to analyze the expected welfare of the allocation returned by our randomized rounding algorithm.

We present a Gaussian random walk in a polytope that starts at a point inside and continues until it gets absorbed at a vertex. Our main result is that the probability distribution induced on the vertices by this random walk has strong negative dependence properties for matroid polytopes. Such distributions are highly sought after in randomized algorithms as they imply concentration properties. Our random walk is simple to implement, computationally efficient and can be viewed as an algorithm to round the starting point in an unbiased manner. The proof relies on a simple inductive argument that synthesizes the combinatorial structure of matroid polytopes with the geometric structure of multivariate Gaussian distributions. Our result not only implies a long line of past results in a unified and transparent manner, but also implies new results about constructing negatively associated distributions for all matroids.

This paper presents an AC magnetic field based High-Definition Personal Area Tracking (PAT) system. A low-power transmitter antenna acts as a reference for three tracker modules. One module, attached to the Head Mount Display (HMD), tracks the position and orientation of user's head and the other two hand-held modules act as an interface device (like virtual hands) in Virtual Reality. This precise, low power, low latency, non-line-of-sight system provides an easy-to-use human-computer interface. The system achieves a precision of 1 mm in position with 0.1 degree in orientation and an accuracy of 20 cm in position at a distance of 2 m from the antenna. The transmitter and the receiver consume 5 W and 0.4 W of power, respectively, providing 140 updates/sec with 11 ms of latency.

Linear programming (LP) 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 the 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 LP relaxation was known to efficiently approximate the problem. In this paper, we present an LP relaxation with a constant integrality gap for the capacitated facility location. We demonstrate that the fundamental theories of multicommodity 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.

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.

We study weighted bipartite edge coloring problem, which is a generalization of two classical problems: bin packing and edge coloring. This problem has been inspired from the study of Clos networks in multirate switching environment in communication networks. In weighted bipartite edge coloring problem, we are given an edge-weighted bipartite multi-graph G=(V,E) with weights w:E\rightarrow [0,1]. The goal is to find a proper weighted coloring of the edges with as few colors as possible. An edge coloring of the weighted graph is called a proper weighted coloring if the sum of the weights of the edges incident to a vertex of any color is at most one. Chung and Ross conjectured 2m-1 colors are sufficient for a proper weighted coloring, where m denotes the minimum number of unit sized bins needed to pack the weights of all edges incident at any vertex. We give an algorithm that returns a coloring with at most \lceil 2.2223m \rceil colors improving on the previous result of \frac{9m}{4} by Feige and Singh. Our algorithm is purely combinatorial and combines the König's theorem for edge coloring bipartite graphs and first-fit decreasing heuristic for bin packing. However, our analysis uses configuration linear program for the bin packing problem to give the improved result.

Modern software applications and services operate nowadays on top of large clusters and datacenters. To reduce the underlying infrastructure cost and increase utilization, different services share the same physical resources (e.g., CPU, bandwidth, I/O, memory). Consequently, the cluster provider often has to decide in real-time how to allocate resources in overbooked systems, taking into account the different characteristics and requirements of users. In this paper, we consider an important problem within this space -- how to share memory between users, whose memory access patterns are unknown in advance. We assume that the overall performance (or cost) of each user is a non-linear function of the total number of misses over a given period of time. We develop an online caching algorithm for arbitrary cost functions. We further provide theoretical guarantees for convex functions (which capture plausible practical scenarios). In particular, our algorithm is αα kα-competitive, where k is the memory (cache) size, and α is a constant which depends on the curvature of the cost functions. We also obtain a bi-criteria result which trades-off the performance and the memory size. Finally, we give a lower bound on the performance of any online deterministic algorithm which nearly matches the upper bound of our algorithm.

In the Minimum Bounded Degree Spanning Tree problem, we are given an undirected graph G = ( V, E ) with a degree upper bound B v on each vertex v ∈ V , and the task is to find a spanning tree of minimum cost that satisfies all the degree bounds. Let OPT be the cost of an optimal solution to this problem. In this article we present a polynomial-time algorithm which returns a spanning tree T of cost 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 a result of Fürer and Raghavachari [1994] to weighted graphs, and settles a conjecture of Goemans [2006] affirmatively. The algorithm generalizes when each vertex v has a degree lower bound A v and a degree upper bound B v , and returns a spanning tree with cost at most OPT and A v - 1 ≤ d T ( v ) ≤ B v + 1 for all v ∈ V . This is essentially the best possible. The main technique used is an extension of the iterative rounding method introduced by Jain [2001] for the design of approximation algorithms.

Relational database-as-a-service (DaaS) providers need to rely on multi-tenancy and resource sharing among tenants, since statically reserving resources for a tenant is not cost effective. A major consequence of resource sharing is that the performance of one tenant can be adversely affected by resource demands of other co-located tenants. One such resource that is essential for good performance of a tenant's workload is buffer pool memory. In this paper, we study the problem of how to effectively share buffer pool memory in multi-tenant relational DaaS. We first develop an SLA framework that defines and enforces accountability of the service provider to the tenant even when buffer pool memory is not statically reserved on behalf of the tenant. Next, we present a novel buffer pool page replacement algorithm (MT-LRU) that builds upon theoretical concepts from weighted online caching, and is designed for multi-tenant scenarios involving SLAs and overbooking. MT-LRU generalizes the LRU-K algorithm which is commonly used in relational database systems. We have prototyped our techniques inside a commercial DaaS engine and extensive experiments demonstrate the effectiveness of our solution.

Spencer's theorem asserts that, for any family of n subsets of ground set of size n, the elements of the ground set can be "colored" by the values +1 or -1 such that the sum of every set is O(sqrt(n)) in absolute value. All existing proofs of this result recursively construct "partial colorings", which assign +1 or -1 values to half of the ground set. We devise the first algorithm for Spencer's theorem that directly computes a coloring, without recursively computing partial colorings.

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.

We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial time 6-approximation algorithm for finding a minimum cost subgraph of an undirected graph G that admits an orientation covering a nonnegative crossing G-supermodular demand function, as defined by Frank [3]. An important example is (k,ℓ) -edge-connectivity, a common generalization of global and rooted edge-connectivity. Our algorithm is based on a non-standard application of the iterative rounding method. We observe that the standard linear program with cut constraints is not amenable and use an alternative linear program with partition and co-partition constraints instead. The proof requires a new type of uncrossing technique on partitions and co-partitions. We also consider the problem setting when the cost of an edge can be different for the two possible orientations. The problem becomes substantially more difficult already for the simpler requirement of k-edge-connectivity. Khanna, Naor and Shepherd [11] showed that the integrality gap of the natural linear program is at most 4 when k = 1 and conjectured that it is constant for all fixed k. We disprove this conjecture by showing an Ω(|V|) integrality gap even when k = 2.

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.

Given a universe $U$ of $n$ elements and a weighted collection $\mathscr{S}$ of $m$ subsets of $U$, the universal set cover problem is to a priori map each element $u \in U$ to a set $S(u) \in \mathscr{S}$ containing $u$ such that any set $X{\subseteq U}$ is covered by $S(X)=\cup_{u\in XS(u)$. The aim is to find 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(\sqrt{n})$ 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 (nonmetric) 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 multicut and disc-covering problems and show how all these universal mappings give us algorithms for the stochastic online variants of the problems with the same competitive factors.

In the minimum bounded degree Steiner network problem, we are given an undirected graph 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 $b_v$ for each vertex $v$. The task is to find a minimum cost subgraph that satisfies all the connectivity requirements and degree upper bounds. Let $r_{\max}:=\max_{u,v} \{r_{uv}\}$ and ${\sc opt}$ be the cost of an optimal solution that satisfies all the degree bounds. We present approximation algorithms that minimize the total cost and the degree violation simultaneously. In the special case when $r_{\max}=1$, there is a polynomial time algorithm that returns a Steiner forest of cost at most $2{\sc opt}$ and the degree of each vertex $v$ is at most $b_v+3$. In the general case, there is a polynomial time algorithm that returns a Steiner network of cost at most $2{\sc opt}$ and the degree of each vertex $v$ is at most $b_v+6r_{\max}+3$. The algorithms are based on the iterative relaxation method, and the analysis of the algorithms is nearly tight.

Testing of high-speed Digital-to-Analog Converters (DACs) is a challenging task, as it requires large number of high-speed synchronized input signals with specific test patterns. To overcome this problem, we propose use of PRBS signals with an “Alternate-Bit-Tapping” technique and eye-diagram measurement as a solution to efficiently generate the test-vectors and test the DACs. This approach covers all levels and transitions necessary for testing the dynamic behavior of the DAC completely, in minimum possible time. Circuit level simulations are used to verify its usefulness in testing a 4-bit 20-GS/s current-steering DAC.

For some positive constant ϵ0, we give a (3/2-ϵ0)-approximation algorithm for the following problem: given a graph G0= (V,V0), 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.

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)).

Wireless mesh networks are popular as a cost- effective means to provide broadband connectivity to large user populations. A mesh network placement provides coverage, such that each target client location has a link to a deployed mesh node, and connectivity, such that each mesh node wirelessly connects directly to a gateway or via intermediate mesh nodes. Prior work on placement assumes wireless propagation to be uniform in all directions, i.e., an unrealistic assumption of circular communication regions. In this paper, we present approximation algorithms to solve the NP- hard mesh node placement problem for non-uniform propagation settings. The first key challenge is incorporating non-uniform propagation, which we address by formulating the problem input as a connectivity graph consisting of discrete target coverage locations and potential mesh node locations. This graph incorporates non-uniform propagation by specifying the estimated signal quality per link. Secondly, our algorithms are the first to minimize the number of deployed mesh nodes with constant-factor approximation ratio in the non-uniform propagation setting. To achieve this, we formulate the Degree-Constrained Terminal Steiner tree problem and present approximation algorithms which leverage prior results on the Steiner tree problem. Third, it is impractical to measure all possible potential mesh links, and therefore deployment planning must rely on estimations. To address this challenge, we extend our algorithm to iteratively measure the links in the solution Steiner tree, refining the graph input on a per-link basis in order to ensure the deployed network is not disconnected. Finally, we use propagation measurements at 35,000 locations in the deployed GoogleWiFi network to investigate placement in a realistic, non-uniform propagation environment. Under this measured propagation setting, our algorithms result in up to 80% fewer mesh nodes than current algorithms and only require an average of 3 measurements per deployed mesh node to ensure backhaul connectivity.

We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds $B_v$ on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a $(2,2B_v+3)$-approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex v is at most $2B_v+3$. This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly k-Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost $\lambda$-edge-connected subgraph with at least k vertices, which we call the $(k,\lambda)$-subgraph problem. This generalizes some well-studied classical problems such as the k-MST and the minimum cost $\lambda$-edge-connected subgraph problems. We give a polylogarithmic approximation for the $(k,2)$-subgraph problem. However, by relating it to the Densest k-Subgraph problem, we provide evidence that the $(k,\lambda)$-subgraph problem might be hard to approximate for arbitrary $\lambda$.

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)=UuepsiXS(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.

We study a general network design problem with additional degree constraints. Given connectivity requirements ruv for all pairs of vertices, a Steiner network is a graph in which there are at least ruv 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 ruv 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.

We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds Bv on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a (2, 2Bv +3)-approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex v is at most 2Bv + 3. This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly k-Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic

In the Minimum Bounded Degree Spanning Tree problem, we aregiven an undirected graph with a degree upper bound Bv 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 dT(v) ≤ Bv+1 for all v, where dT(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 Av and a degree upper bound Bv, andreturns a spanning tree with cost at most OPT and Av - 1 ≤dT(v) ≤ Bv + 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.

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.