5 citations · 8 across the 10 of their papers we have counts for
12 papers
Treewidth and the complexity of box-constrained quadratic programs
Alberto Del Pia, Aida Khajavirad
We consider the problem of minimizing a sparse quadratic function over the unit hypercube. In binary quadratic programming, treewidth of the interaction graph is a central paramete…
The complete edge relaxation for binary polynomial optimization
Alberto Del Pia, Aida Khajavirad
We consider the multilinear polytope, defined as the convex hull of the feasible region of a lifted binary polynomial optimization problem. We define a relaxation in an extended sp…
Extended formulations for the multilinear polytope of acyclic hypergraphs
Alberto Del Pia, Aida Khajavirad
This article provides an overview of our joint work on binary polynomial optimization over the past decade. We define the multilinear polytope as the convex hull of the feasible re…
Beyond hypergraph acyclicity: limits of tractability for pseudo-Boolean optimization
Alberto Del Pia, Aida Khajavirad
In this paper, we study the problem of minimizing a polynomial function with literals over all binary points, often referred to as pseudo-Boolean optimization. We investigate the f…
The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
Alberto Del Pia, Aida Khajavirad
With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the convex hull of the set of binary…
A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
Alberto Del Pia, Aida Khajavirad
We consider the multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. The complexity of the facial structure…
On the strength of recursive McCormick relaxations for binary polynomial optimization
Aida Khajavirad
Recursive McCormick relaxations have been among the most popular convexification techniques for binary polynomial optimization problems. It is well-understood that both the quality…
Explicit convex hull description of bivariate quadratic sets with indicator variables
Antonio De Rosa, Aida Khajavirad
We consider the nonconvex set , which is closely related to the feasible region of several diff…
Rank-one Boolean tensor factorization and the multilinear polytope
Alberto Del Pia, Aida Khajavirad
We consider the NP-hard problem of finding the closest rank-one binary tensor to a given binary tensor, which we refer to as the rank-one Boolean tensor factorization (BTF) problem…
Efficient Joint Object Matching via Linear Programming
Antonio De Rosa, Aida Khajavirad
Joint object matching, also known as multi-image matching, namely, the problem of finding consistent partial maps among all pairs of objects within a collection, is a crucial task…
The ratio-cut polytope and K-means clustering
Antonio De Rosa, Aida Khajavirad
We introduce the ratio-cut polytope defined as the convex hull of ratio-cut vectors corresponding to all partitions of points in into at most clusters. This p…
Linear Programming and Community Detection
Alberto Del Pia, Aida Khajavirad, Dmitriy Kunisky
The problem of community detection with two equal-sized communities is closely related to the minimum graph bisection problem over certain random graph models. In the stochastic bl…