Source author record

Bento Natura

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.OC Computational Geometry Discrete Mathematics

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Faster Interior-Point Method for Sum-of-Squares Optimization

We present a faster interior-point method for optimizing sum-of-squares (SOS) polynomials, which are a central tool in polynomial optimization and capture convex programming in the Lasserre hierarchy. Let $p = \sum_i q^2_i$ be an $n$ -variate SOS polynomial of degree $2d$ . Denoting by $L := \binom{n+d}{d}$ and $U := \binom{n+2d}{2d}$ the dimensions of the vector spaces in which $q_i$ 's and $p$ live respectively, our algorithm runs in time $\tilde{O}(LU^{1.87})$ . This is polynomially faster than state-of-art SOS and semidefinite programming solvers, which achieve runtime $\tilde{O}(L^{0.5}\min\{U^{2.37}, L^{4.24}\})$ . The centerpiece of our algorithm is a dynamic data structure for maintaining the inverse of the Hessian of the SOS barrier function under the polynomial interpolant basis, which efficiently extends to multivariate SOS optimization, and requires maintaining spectral approximations to low-rank perturbations of elementwise (Hadamard) products. This is the main challenge and departure from recent IPM breakthroughs using inverse-maintenance, where low-rank updates to the slack matrix readily imply the same for the Hessian matrix.

preprint2022arXiv

The Pareto cover problem

We introduce the problem of finding a set $B$ of $k$ points in $[0,1]^n$ such that the expected cost of the cheapest point in $B$ that dominates a random point from $[0,1]^n$ is minimized. We study the case where the coordinates of the random points are independently distributed and the cost function is linear. This problem arises naturally in various application areas where customers' requests are satisfied based on predefined products, each corresponding to a subset of features. We show that the problem is NP-hard already for $k=2$ when each coordinate is drawn from $\{0,1\}$ , and obtain an FPTAS for general fixed $k$ under mild assumptions on the distributions.

preprint2020arXiv

Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers

In breakthrough work, Tardos (Oper. Res. '86) gave a proximity based framework for solving linear programming (LP) in time depending only on the constraint matrix in the bit complexity model. In Tardos's framework, one reduces solving the LP $\min \langle c,{x}\rangle$ , $Ax=b$ , $x \geq 0$ , $A \in \mathbb{Z}^{m \times n}$ , to solving $O(nm)$ LPs in $A$ having small integer coefficient objectives and right-hand sides using any exact LP algorithm. This gives rise to an LP algorithm in time poly $(n,m\logΔ_A)$ , where $Δ_A$ is the largest subdeterminant of $A$ . A significant extension to the real model of computation was given by Vavasis and Ye (Math. Prog. '96), giving a specialized interior point method that runs in time poly $(n,m,\log\barχ_A)$ , depending on Stewart's $\barχ_A$ , a well-studied condition number. In this work, we extend Tardos's original framework to obtain such a running time dependence. In particular, we replace the exact LP solves with approximate ones, enabling us to directly leverage the tremendous recent algorithmic progress for approximate linear programming. More precisely, we show that the fundamental "accuracy" needed to exactly solve any LP in $A$ is inverse polynomial in $n$ and $\log\barχ_A$ . Plugging in the recent algorithm of van den Brand (SODA '20), our method computes an optimal primal and dual solution using ${O}(m n^{ω+1} \log (n)\log(\barχ_A+n))$ arithmetic operations, outperforming the specialized interior point method of Vavasis and Ye and its recent improvement by Dadush et al (STOC '20). At a technical level, our framework combines together approximate LP solutions to compute exact ones, making use of constructive proximity theorems -- which bound the distance between solutions of "nearby" LPs -- to keep the required accuracy low.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.