Source author record

Alejandro Cassis

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 Computational Complexity

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Structural Investigation of the Approximability of Polynomial-Time Problems

We initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest Neighbor in the Hamming metric, Maximum Inner Product, optimization variants of $k$ -XOR and Maximum $k$ -Cover). Specifically, MaxSP $_k$ denotes the class of $O(m^k)$ -time problems of the form $\max_{x_1,\dots, x_k} \#\{y:ϕ(x_1,\dots,x_k,y)\}$ where $ϕ$ is a quantifier-free first-order property and $m$ denotes the size of the relational structure. Assuming central hypotheses about clique detection in hypergraphs and MAX3SAT, we show that for any MaxSP $_k$ problem definable by a quantifier-free $m$ -edge graph formula $ϕ$ , the best possible approximation guarantee in faster-than-exhaustive-search time $O(m^{k-δ})$ falls into one of four categories: * optimizable to exactness in time $O(m^{k-δ})$ , * an (inefficient) approximation scheme, i.e., a $(1+ε)$ -approximation in time $O(m^{k-f(ε)})$ , * a (fixed) constant-factor approximation in time $O(m^{k-δ})$ , or * an $m^ε$ -approximation in time $O(m^{k-f(ε)})$ . We obtain an almost complete characterization of these regimes, for MaxSP $_k$ as well as for an analogously defined minimization class MinSP $_k$ . As our main technical contribution, we rule out approximation schemes for a large class of problems admitting constant-factor approximations, under the Sparse MAX3SAT hypothesis posed by (Alman, Vassilevska Williams'20). As general trends for the problems we consider, we find: (1) Exact optimizability has a simple algebraic characterization, (2) only few maximization problems do not admit a constant-factor approximation; these do not even have a subpolynomial-factor approximation, and (3) constant-factor approximation of minimization problems is equivalent to deciding whether the optimum is equal to 0.

preprint2022arXiv

Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution

We present new exact and approximation algorithms for 0-1-Knapsack and Unbounded Knapsack: * Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running in time $\widetilde{O}(n + \min\{n OPT, n W, OPT^2, W^2\})$ , where $n$ is the number of items, $W$ is the weight budget, and $OPT$ is the optimal profit. We present an algorithm running in time $\widetilde{O}(n + (W + OPT)^{1.5})$ . This improves the running time in case $n,W,OPT$ are roughly equal. * Exact Algorithm for Unbounded Knapsack: Unbounded Knapsack has known algorithms running in time $\widetilde{O}(n + \min\{n \cdot p_{\max}, n \cdot w_{\max}, p_{\max}^2, w_{\max}^2\})$ [Axiotis, Tzamos '19, Jansen, Rohwedder '19, Chan, He '20], where $n$ is the number of items, $w_{\max}$ is the largest weight of any item, and $p_{\max}$ is the largest profit of any item. We present an algorithm running in time $\widetilde{O}(n + (p_{\max} + w_{\max})^{1.5})$ , giving a similar improvement as for 0-1-Knapsack. * Approximating Unbounded Knapsack with Resource Augmentation: Unbounded Knapsack has a known FPTAS with running time $\widetilde{O}(\min\{n/\varepsilon, n + 1/\varepsilon^2\})$ [Jansen, Kraft '18]. We study weak approximation algorithms, which approximate the optimal profit but are allowed to overshoot the weight constraint. We present the first approximation scheme for Unbounded Knapsack in this setting, achieving running time $\widetilde{O}(n + 1/\varepsilon^{1.5})$ . Our algorithms can be seen as reductions to Min-Plus-Convolution on monotone sequences with bounded entries. These structured instances of Min-Plus-Convolution can be solved in time $O(n^{1.5})$ [Chi,Duan,Xie,Zhang '22] (in contrast to the conjectured $n^{2-o(1)}$ lower bound for the general case).

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.