Search

This paper presents a general refractive camera model and online co-estimation of odometry and the refractive index of 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., Comment: Accepted at the 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2024), 8 pages

This study applies Natural Language Processing techniques, including Latent Dirichlet Allocation, to analyse anonymised maternity incident investigation reports from the Healthcare Safety Investigation Branch. The reports underwent preprocessing, annotation using the Safety Intelligence Research taxonomy, and topic modelling to uncover prevalent topics and detect differences in maternity care across ethnic groups. A combination of offline and online methods was utilised to ensure data protection whilst enabling advanced analysis, with offline processing for sensitive data and online processing for non-sensitive data using the `Claude 3 Opus' language model. Interactive topic analysis and semantic network visualisation were employed to extract and display thematic topics and visualise semantic relationships among keywords. The analysis revealed disparities in care among different ethnic groups, with distinct focus areas for the Black, Asian, and White British ethnic groups. The study demonstrates the effectiveness of topic modelling and NLP techniques in analysing maternity incident investigation reports and highlighting disparities in care. The findings emphasise the crucial role of advanced data analysis in improving maternity care quality and equity.

In healthcare, thousands of safety incidents occur every year, but learning from these incidents is not effectively aggregated. Analysing incident reports using AI could uncover critical insights to prevent harm by identifying recurring patterns and contributing factors. To aggregate and extract valuable information, natural language processing (NLP) and machine learning techniques can be employed to summarise and mine unstructured data, potentially surfacing systemic issues and priority areas for improvement. This paper presents I-SIRch:CS, a framework designed to facilitate the aggregation and analysis of safety incident reports while ensuring traceability throughout the process. The framework integrates concept annotation using the Safety Intelligence Research (SIRch) taxonomy with clustering, summarisation, and analysis capabilities. Utilising a dataset of 188 anonymised maternity investigation reports annotated with 27 SIRch human factors concepts, I-SIRch:CS groups the annotated sentences into clusters using sentence embeddings and k-means clustering, maintaining traceability via file and sentence IDs. Summaries are generated for each cluster using offline state-of-the-art abstractive summarisation models (BART, DistilBART, T5), which are evaluated and compared using metrics assessing summary quality attributes. The generated summaries are linked back to the original file and sentence IDs, ensuring traceability and allowing for verification of the summarised information. Results demonstrate BART's strengths in creating informative and concise summaries.

Maternity care is a complex system involving treatments and interactions between patients, providers, and the care environment. To improve patient safety and outcomes, understanding the human factors (e.g. individuals decisions, local facilities) influencing healthcare delivery is crucial. However, most current tools for analysing healthcare data focus only on biomedical concepts (e.g. health conditions, procedures and tests), overlooking the importance of human factors. We developed a new approach called I-SIRch, using artificial intelligence to automatically identify and label human factors concepts in maternity healthcare investigation reports describing adverse maternity incidents produced by England's Healthcare Safety Investigation Branch (HSIB). These incident investigation reports aim to identify opportunities for learning and improving maternal safety across the entire healthcare system. I-SIRch was trained using real data and tested on both real and simulated data to evaluate its performance in identifying human factors concepts. When applied to real reports, the model achieved a high level of accuracy, correctly identifying relevant concepts in 90\% of the sentences from 97 reports. Applying I-SIRch to analyse these reports revealed that certain human factors disproportionately affected mothers from different ethnic groups. Our work demonstrates the potential of using automated tools to identify human factors concepts in maternity incident investigation reports, rather than focusing solely on biomedical concepts. This approach opens up new possibilities for understanding the complex interplay between social, technical, and organisational factors influencing maternal safety and population health outcomes. By taking a more comprehensive view of maternal healthcare delivery, we can develop targeted interventions to address disparities and improve maternal outcomes.

In an instance of the minimum eigenvalue problem, we are given a collection of $n$ vectors $v_1,\ldots, v_n \subset {\mathbb{R}^d}$, and the goal is to pick a subset $B\subseteq [n]$ of given vectors to maximize the minimum eigenvalue of the matrix $\sum_{i\in B} v_i v_i^{\top} $. Often, additional combinatorial constraints such as cardinality constraint $\left(|B|\leq k\right)$ or matroid constraint ($B$ is a basis of a matroid defined on $[n]$) must be satisfied by the chosen set of vectors. The minimum eigenvalue problem with matroid constraints models a wide variety of problems including the Santa Clause problem, the E-design problem, and the constructive Kadison-Singer problem. In this paper, we give a randomized algorithm that finds a set $B\subseteq [n]$ subject to any matroid constraint whose minimum eigenvalue is at least $(1-\epsilon)$ times the optimum, with high probability. The running time of the algorithm is $O\left( n^{O(d\log(d)/\epsilon^2)}\right)$. In particular, our results give a polynomial time asymptotic scheme when the dimension of the vectors is constant. Our algorithm uses a convex programming relaxation of the problem after guessing a rescaling which allows us to apply pipage rounding and matrix Chernoff inequalities to round to a good solution. The key new component is a structural lemma which enables us to "guess'' the appropriate rescaling, which could be of independent interest. Our approach generalizes the approximation guarantee to monotone, homogeneous functions and as such we can maximize $\det(\sum_{i\in B} v_i v_i^\top)^{1/d}$, or minimize any norm of the eigenvalues of the matrix $\left(\sum_{i\in B} v_i v_i^\top\right)^{-1} $, with the same running time under some mild assumptions. As a byproduct, we also get a simple algorithm for an algorithmic version of Kadison-Singer problem.

In an instance of the weighted Nash Social Welfare problem, we are given a set of $m$ indivisible items, $\mathscr{G}$, and $n$ agents, $\mathscr{A}$, where each agent $i \in \mathscr{A}$ has a valuation $v_{ij}\geq 0$ for each item $j\in \mathscr{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 $\sigma:\mathscr{G}\rightarrow \mathscr{A}$ that maximizes $\prod_{i\in \mathscr{A}} \left(\sum_{j\in \sigma^{-1}(i)} v_{ij}\right)^{w_i}$, the product of the weighted valuations of the players. When all the weights equal $\frac1n$, the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present a $5\cdot\exp\left(2\cdot D_{\text{KL}}(\mathbf{w}\, ||\, \frac{\vec{\mathbf{1}}}{n})\right) = 5\cdot\exp\left(2\log{n} + 2\sum_{i=1}^n w_i \log{w_i}\right)$-approximation algorithm for the weighted Nash Social Welfare problem, where $D_{\text{KL}}(\mathbf{w}\, ||\, \frac{\vec{\mathbf{1}}}{n})$ denotes the KL-divergence between the distribution induced by $\mathbf{w}$ and the uniform distribution on $[n]$. We show a novel connection between the convex programming relaxations for the unweighted variant of Nash Social Welfare presented in \cite{cole2017convex, anari2017nash}, and generalize the programs to two different mathematical programs for the weighted case. 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.

Motivated by fairness concerns, we study the `portfolio problem': given an optimization problem with set $D$ of feasible solutions, a class $\mathbf{C}$ of fairness objective functions on $D$, and an approximation factor $\alpha \ge 1$, a set $X \subseteq D$ of feasible solutions is an $\alpha$-approximate portfolio if for each objective $f \in \mathbf{C}$, there is an $\alpha$-approximation for $f$ in $X$. Choosing the classes of top-$k$ norms, ordered norms, and symmetric monotonic norms as our equity objectives, we study the trade-off between the size $|X|$ of the portfolio and its approximation factor $\alpha$ for various combinatorial problems. For the problem of scheduling identical jobs on unidentical machines, we characterize this trade-off for ordered norms and give an exponential improvement in size for symmetric monotonic norms over the general upper bound. We generalize this result as the OrderAndCount framework that obtains an exponential improvement in portfolio sizes for covering polyhedra with a constant number of constraints. Our framework is based on a novel primal-dual counting technique that may be of independent interest. We also introduce a general IterativeOrdering framework for simultaneous approximations or portfolios of size $1$ for symmetric monotonic norms, which generalizes and extends existing results for problems such as scheduling, $k$-clustering, set cover, and routing., Comment: 40 pages, 3 figures

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., Comment: 7 pages, 6 figures, Submitted to the IEEE International Conference on Robotics and Automation, 2024

Multiple TSP ($\mathrm{mTSP}$) is a important variant of $\mathrm{TSP}$ where a set of $k$ salesperson together visit a set of $n$ cities. The $\mathrm{mTSP}$ problem has applications to many real life applications such as vehicle routing. Rothkopf introduced another variant of $\mathrm{TSP}$ called many-visits TSP ($\mathrm{MV\mbox{-}TSP}$) where a request $r(v)\in \mathbb{Z}_+$ is given for each city $v$ and a single salesperson needs to visit each city $r(v)$ times and return back to his starting point. A combination of $\mathrm{mTSP}$ and $\mathrm{MV\mbox{-}TSP}$ called many-visits multiple TSP $(\mathrm{MV\mbox{-}mTSP})$ was studied by B\'erczi, Mnich, and Vincze where the authors give approximation algorithms for various variants of $\mathrm{MV\mbox{-}mTSP}$. In this work, we show a simple linear programming (LP) based reduction that converts a $\mathrm{mTSP}$ LP-based algorithm to a LP-based algorithm for $\mathrm{MV\mbox{-}mTSP}$ with the same approximation factor. We apply this reduction to improve or match the current best approximation factors of several variants of the $\mathrm{MV\mbox{-}mTSP}$. Our reduction shows that the addition of visit requests $r(v)$ to $\mathrm{mTSP}$ does $\textit{not}$ make the problem harder to approximate even when $r(v)$ is exponential in number of vertices. To apply our reduction, we either use existing LP-based algorithms for $\mathrm{mTSP}$ variants or show that several existing combinatorial algorithms for $\mathrm{mTSP}$ variants can be interpreted as LP-based algorithms. This allows us to apply our reduction to these combinatorial algorithms as well achieving the improved guarantees.

We consider the Max-$3$-Section problem, where we are given an undirected graph $ G=(V,E)$ equipped with non-negative edge weights $w :E\rightarrow \mathbb{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-$k$-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.

Fair facility location problems try to balance access costs to open facilities borne by different groups of people by minimizing the $L_p$ norm of these group distances. However, there is no clear choice of "$p$" in the current literature. We present a novel approach to address the challenge of choosing the right notion of fairness. We introduce the concept of portfolios, a set of solutions that contains an approximately optimal solution for each objective in a given class of objectives, such as $L_p$ norms. This concept opens up new possibilities for getting around the "right" notion of fairness for many problems. For $r$ client groups, we demonstrate portfolios of size $\Theta(\log r)$ for the facility location and $k$-clustering problems, with an $O(1)$-approximate solution for each $L_p$ norm. Further, motivated by the Justice40 Initiative that provides rolling budget investments, we impose a refinement-like structure on the portfolio. We develop novel approximation algorithms for these structured portfolios and show experimental evidence of their performance in two US counties. We also present a planning tool that provides potential ways to expand access to US healthcare facilities, which might be of independent interest to policymakers., Comment: A preliminary version of this article appeared as a one-page extended abstract in the proceedings of Economics and Computation (EC) 2023 conference

Determinant maximization provides an elegant generalization of problems in many areas, including convex geometry, statistics, machine learning, fair allocation of goods, and network design. In an instance of the determinant maximization problem, we are given a collection of vectors $v_1,\ldots, v_n \in \mathbb{R}^d$, and the goal is to pick a subset $S\subseteq [n]$ of given vectors to maximize the determinant of the matrix $\sum_{i \in S} v_iv_i^\top$, where the picked set of vectors $S$ must satisfy some combinatorial constraint such as cardinality constraint ($|S| \leq k$) or matroid constraint ($S$ is a basis of a matroid defined on $[n]$). In this work, we give a combinatorial algorithm for the determinant maximization problem under a matroid constraint that achieves $O(d^{O(d)})$-approximation for any matroid of rank $r\geq d$. This complements the recent result of~\cite{BrownLPST22} that achieves a similar bound for matroids of rank $r\leq d$, relying on a geometric interpretation of the determinant. Our result matches the best-known estimation algorithms~\cite{madan2020maximizing} for the problem, which could estimate the objective value but could not give an approximate solution with a similar guarantee. Our work follows the framework developed by~\cite{BrownLPST22} of using matroid intersection based algorithms for determinant maximization. To overcome the lack of a simple geometric interpretation of the objective when $r \geq d$, our approach combines ideas from combinatorial optimization with algebraic properties of the determinant. We also critically use the properties of a convex programming relaxation of the problem introduced by~\cite{madan2020maximizing}.

In online sales, sellers usually offer each potential buyer a posted price in a take-it-or-leave fashion. Buyers can sometimes see posted prices faced by other buyers, and changing the price frequently could be considered unfair. The literature on posted price mechanisms and prophet inequality problems has studied the two extremes of pricing policies, the fixed price policy and fully dynamic pricing. The former is suboptimal in revenue but is perceived as fairer than the latter. This work examines the middle situation, where there are at most $k$ distinct prices over the selling horizon. Using the framework of prophet inequalities with independent and identically distributed random variables, we propose a new prophet inequality for strategies that use at most $k$ thresholds. We present asymptotic results in $k$ and results for small values of $k$. For $k=2$ prices, we show an improvement of at least $11\%$ over the best fixed-price solution. Moreover, $k=5$ prices suffice to guarantee almost $99\%$ of the approximation factor obtained by a fully dynamic policy that uses an arbitrary number of prices. From a technical standpoint, we use an infinite-dimensional linear program in our analysis; this formulation could be of independent interest to other online selection problems.

Anisotropic particles oriented in a specific direction can act as artificial atoms and molecules, and their controlled assembly can result in a wide variety of ordered structures. Towards this, we demonstrate the orientation transitions of uncharged peanut-shaped polystyrene colloids, suspended in a non-ionic aprotic polar solvent, near a flat surface whose potential is static or time-varying. The charged surface is coated with an insulating dielectric layer to suppress electric currents. The transition between several orientation states such as random, normal or parallel orientation with respect to the surface, is examined for two different colloid sizes at low-frequency ($\sim 10-350$ kHz) or static fields, and at small electric potentials. In time-varying (AC) field, a detailed phase diagram in the potential-frequency plane indicating the transition between particles parallel or normal to the surface is reported. We next present the first study of orientation switching in static (DC) fields, where no electro-osmotic or other flow is present. A reversible change between the two colloidal states is explained by a theory showing that the sum of electrostatic and gravitational energies of the colloid is bistable. The number of colloids in each of the two states depends on the external potential, particle and solvent permittivities, particle aspect ratio, and distance from the electrode., Comment: 19 pages, 8 figures, accepted to Colloids and Surfaces A: Physicochemical and Engineering Aspects (2022)

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics \cite{pukelsheim2006optimal}, convex geometry \cite{Khachiyan1996}, fair allocations\linebreak \cite{anari2016nash}, combinatorics \cite{AnariGV18}, spectral graph theory \cite{nikolov2019proportional}, network design, and random processes \cite{kulesza2012determinantal}. In an instance of a determinant maximization problem, we are given a collection of vectors $U=\{v_1,\ldots, v_n\} \subset \RR^d$, and a goal is to pick a subset $S\subseteq U$ of given vectors to maximize the determinant of the matrix $\sum_{i\in S} v_i v_i^\top $. Often, the set $S$ of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint $\left(|S|\leq k\right)$ 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 \emph{estimation} algorithms \cite{NikolovS16,anari2017generalization,AnariGV18,madan2020maximizing} for any $r\leq d$. All previous results use convex relaxations and their relationship to stable polynomials and strongly log-concave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an \emph{alternating negative cycle} in the \emph{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 study approximation algorithms for the socially fair $(\ell_p, k)$-clustering problem with $m$ groups, whose special cases include the socially fair $k$-median ($p=1$) and socially fair $k$-means ($p=2$) problems. We present (1) a polynomial-time $(5+2\sqrt{6})^p$-approximation with at most $k+m$ centers (2) a $(5+2\sqrt{6}+\epsilon)^p$-approximation with $k$ centers in time $n^{2^{O(p)}\cdot m^2}$, and (3) a $(15+6\sqrt{6})^p$ approximation with $k$ centers in time $k^{m}\cdot\text{poly}(n)$. The first result is obtained via a refinement of the iterative rounding method using a sequence of linear programs. The latter two results are obtained by converting a solution with up to $k+m$ centers to one with $k$ centers using sparsification methods for (2) and via an exhaustive search for (3). We also compare the performance of our algorithms with existing bicriteria algorithms as well as exactly $k$ center approximation algorithms on benchmark datasets, and find that our algorithms also outperform existing methods in practice., Comment: 18 pages, 7 figures, 6 tables

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.

We investigate the aerodynamic efficiency and flight dynamics of mono-wing and box-wing configurations across various parameters, including aspect ratio, velocity, and lift requirements. We find that although mono-wing configurations exhibit superior aerodynamic efficiency in certain regimes, box-wing designs perform better in circumstances like high velocities and increased lift demands. Box-wing configurations also prove advantageous when induced drag is higher than friction drag due to their ability to suppress the tip vortices. Furthermore, while analyzing the flight dynamics, low aspect ratio box-wing configurations show improved gust tolerance and stability in longitudinal and lateral dynamics. However, no substantial difference in flight dynamics is observed between box-wing and mono-wing designs for high aspect ratio configurations. The findings underscore the importance of selecting the appropriate wing configuration based on specific performance requirements and operational conditions., Comment: Manuscript accepted for presentation at the 2025 AIAA SciTech Forum

Online advertising has motivated interest in online selection problems. Displaying ads to the right users benefits both the platform (e.g., via pay-per-click) and the advertisers (by increasing their reach). In practice, not all users click on displayed ads, while the platform's algorithm may miss the users most disposed to do so. This mismatch decreases the platform's revenue and the advertiser's chances to reach the right customers. With this motivation, we propose a secretary problem where a candidate may or may not accept an offer according to a known probability $p$. Because we do not know the top candidate willing to accept an offer, the goal is to maximize a robust objective defined as the minimum over integers $k$ of the probability of choosing one of the top $k$ candidates, given that one of these candidates will accept an offer. Using Markov decision process theory, we derive a linear program for this max-min objective whose solution encodes an optimal policy. The derivation may be of independent interest, as it is generalizable and can be used to obtain linear programs for many online selection models. We further relax this linear program into an infinite counterpart, which we use to provide bounds for the objective and closed-form policies. For $p \geq p^* \approx 0.6$, an optimal policy is a simple threshold rule that observes the first $p^{1/(1-p)}$ fraction of candidates and subsequently makes offers to the best candidate observed so far.

An experimental technique is developed to simultaneously measure both temporal and spatial coherences of a light source by altering a standard Michelson interferometer, which has been primarily used for measuring temporal coherence only. Instead of using simple plane mirrors, two retroreflectors and their longitudinal and lateral movements are utilized to incorporate spatial coherence measurement using this modified Michelson interferometer. In general, one uses Young double slit interferometer to measure spatial coherence. However, this modified interferometer can be used as an optical setup kept at room temperature outside a cryostat to measure spatio-temporal coherence of a light source placed at cryogenic temperatures. This avoids the added complexities of modulation of interference fringe patterns due to single slit diffraction as well. The process of mixing of spatial and temporal parts of coherences is intrinsic to existing methods for dual measurements. We addressed these issues of spatiotemporal mixing and we introduced a method of temporal filtering in spatial coherence measurements. We also developed a curve overlap method which is used to extend the range of the experimental setup during temporal coherence measurements without compromising the precision. Together, these methods provide major advantages over plane mirror based standard interferometric systems for dual measurements in avoiding systematic errors which lead to inaccuracies especially for light sources with low coherences., Comment: 26 pages, 7 figures

Presence of coherent resonant tunneling in quantum dot (zero-dimensional) - quantum well (two-dimensional) heterostructure is necessary to explain the collective oscillations of average electrical polarization of excitonic dipoles over a macroscopically large area. This was measured using photo excited capacitance as a function of applied voltage bias. Resonant tunneling in this heterostructure definitely requires momentum space narrowing of charge carriers inside the quantum well and that of associated indirect excitons, which indicates bias dependent itinerant Bose-Einstein condensation of excitons. Observation of periodic variations in negative quantum capacitance points to in-plane coulomb correlations mediated by long range spatial ordering of indirect, dipolar excitons. Enhanced contrast of quantum interference beats of excitonic polarization waves even under white light and observed Rabi oscillations over a macroscopically large area also support the presence of density driven excitonic condensation having long range order. Periodic presence (absence) of splitting of excitonic peaks in photocapacitance spectra even demonstrate collective coupling (decoupling) between energy levels of the quantum well and quantum dots with applied biases, which can potentially be used for quantum gate operations. All these observations point to experimental control of macroscopically large, quantum state of a two-component Bose-Einstein condensate of excitons in this quantum dot - quantum well heterostructure. Therefore, in principle, millions of two-level excitonic qubits can be intertwined to fabricate large quantum registers using such hybrid heterostructure by controlling the local electric fields and also by varying photoexcitation intensities of overlapping light spots., Comment: 53 pages, Manuscript + 14 Figures

In this paper, we consider the rank-one tensor completion problem. We address the question of existence and uniqueness of the rank-one solution. In particular we show that the global uniqueness over the field of real numbers can be verified in a polynomial time. We give examples showing that there is an essential difference between the question of global uniqueness over the fields of real and complex numbers. Finally we briefly discuss the rank-one approximation problem for noisy observations.

Motivated by bursty bandwidth allocation and by the allocation of virtual machines to servers in the cloud, we consider the online problem of packing items with random sizes into unit-capacity bins. Items arrive sequentially, but upon arrival an item's actual size is unknown; only its probabilistic information is available to the decision maker. Without knowing this size, the decision maker must irrevocably pack the item into an available bin or place it in a new bin. Once packed in a bin, the decision maker observes the item's actual size, and overflowing the bin is a possibility. An overflow incurs a large penalty cost and the corresponding bin is unusable for the rest of the process. In practical terms, this overflow models delayed services, failure of servers, and/or loss of end-user goodwill. The objective is to minimize the total expected cost given by the sum of the number of opened bins and the overflow penalty cost. We present an online algorithm with expected cost at most a constant factor times the cost incurred by the optimal packing policy when item sizes are drawn from an i.i.d. sequence of unknown length. We give a similar result when item size distributions are exponential with arbitrary rates. We also study the offline model, where distributions are known in advance but must be packed sequentially. We construct a soft-capacity PTAS for this problem, and show that the complexity of computing the optimal offline cost is $\#\mathbf{P}$-hard. Finally, we provide an empirical study of our online algorithm's performance.

Given vectors $v_1,\dots,v_n\in\mathbb{R}^d$ and a matroid $M=([n],I)$, we study the problem of finding a basis $S$ of $M$ such that $\det(\sum_{i \in S}v_i 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$ and a $(1+\epsilon)^d$-approximation for a uniform matroid of rank $k\ge d+\frac d\epsilon$, where the rank $k\ge d$ denotes the desired size of the optimal set. Our main result is a new approximation algorithm 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 the existence of 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 randomized algorithm that rounds a sparse fractional solution to a feasible integral solution to the original problem. To show the approximation guarantee, we utilize recent works on strongly log-concave polynomials and show new relationships between different convex programs studied for the problem. Finally, we use the estimation algorithm and sparsity results to give an efficient deterministic approximation algorithm with an approximation guarantee that depends solely on the dimension $d$.

A graph profile records all possible densities of a fixed finite set of graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known, and little is known about hypergraph profiles. We introduce the tropicalization of graph and hypergraph profiles. Tropicalization is a well-studied operation in algebraic geometry, which replaces a variety (the set of real or complex solutions to a finite set of algebraic equations) with its "combinatorial shadow". We prove that the tropicalization of a graph profile is a closed convex cone, which still captures interesting combinatorial information. We explicitly compute these tropicalizations for arbitrary sets of complete and star hypergraphs. We show they are rational polyhedral cones even though the corresponding profiles are not even known to be semialgebraic in some of these cases. We then use tropicalization to prove strong restrictions on the power of the sums of squares method, equivalently Cauchy-Schwarz calculus, to test (which is weaker than certification) the validity of graph density inequalities. In particular, we show that sums of squares cannot test simple binomial graph density inequalities, or even their approximations. Small concrete examples of such inequalities are presented, and include the famous Blakley-Roy inequalities for paths of odd length. As a consequence, these simple inequalities cannot be written as a rational sum of squares of graph densities., Comment: 29 pages, corrected small typos and changed the exposition of Lemma 2.2

Bobkov, Houdr\'e, and the last author [2000] introduced a Poincar\'e-type functional parameter, $\lambda_\infty$, of a graph and related it to connectivity of the graph via Cheeger-type inequalities. A work by the second author, Raghavendra, and Vempala [2013] related the complexity of $\lambda_\infty$ to the so-called small-set expansion (SSE) problem and further set forth the desiderata for NP-hardness of this optimization problem. We confirm the conjecture that computing $\lambda_\infty$ is NP-hard for weighted trees. Beyond measuring connectivity in many applications we want to optimize it. This, via convex duality, leads to a problem in machine learning known as the Maximum Variance Embedding (MVE). The output is a function from vertices to a low dim Euclidean space, subject to bounds on Euclidean distances between neighbors. The objective is to maximize output variance. Special cases of MVE into $n$ and $1$ dims lead to absolute algebraic connectivity [1990] and spread constant [1998], that measure connectivity of the graph and its Cartesian $n$-power, respectively. MVE has other applications in measuring diffusion speed and robustness of networks, clustering, and dimension reduction. We show that computing MVE in tree-width dims is NP-hard, while only one additional dim beyond width of a given tree-decomposition makes the problem in P. We show that MVE of a tree in 2 dims defines a non-convex yet benign optimization landscape, i.e., local=global optima. We further develop a linear time combinatorial algorithm for this case. Finally, we denote approximate Maximum Variance Embedding is tractable in significantly lower dims. For trees and general graphs, for which Maximum Variance Embedding cannot be solved in less than $2$ and $\Omega(n)$ dims, we provide $1+\varepsilon$ approximation algorithms for embedding into $1$ and $O(\log n /\varepsilon^2)$ dims, respectively.