The CONGEST and CONGEST-CLIQUE models have been carefully studied to represent situations where the communication bandwidth between processors in a network is severely limited. Messages of only \( O(log(n)) \) bits of information each may be sent between processors in each round. The quantum versions of these models allow the processors instead to communicate and … Read more
The set partitioning problem and its decision variant (i.e., the exact cover problem) are combinatorial optimization problems that were historically crucial in the quantum optimization community. This problem is also employed in the main problem of the branch-and-price approach in many real-world optimization problems, including, but not limited to, redistricting and scheduling. Motivated by recent … Read more
It is well-known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a … Read more
A common assumption in the models for the vehicle routing problem with stochastic demands is that all demands must be satisfied. This is achieved by including recourse actions in two-stage stochastic programming formulations or by ensuring with a high probability that all demand fits within the vehicle capacity (chance-constrained formulations). In this work, we relax … Read more
In the past decade, deep learning became the prevalent methodology for predictive modeling thanks to the remarkable accuracy of deep neural networks in tasks such as computer vision and natural language processing. Meanwhile, the structure of neural networks converged back to simpler representations based on piecewise constant and piecewise linear functions such as the Rectified … Read more
Given two nonempty and disjoint intersections of closed and convex subsets, we look for a best approximation pair relative to them, i.e., a pair of points, one in each intersection, attaining the minimum distance between the disjoint intersections. We propose an iterative process based on projections onto the subsets which generate the intersections. The process … Read more
In this paper, we introduce cameras view-frame placement problem (denoted by CFP) in the presence an adversary whose objective is to minimize the maximum coverage by p cameras in response to input provided by n autonomous agents in a remote location. We allow uncertainty in the success of attacks, incomplete information of the probability distribution … Read more
We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator \( \text{LS}_+\), with a particular focus on a search for relatively small graphs with high \( \text{LS}_+\)-rank (the least number of iterations of the \( \text{LS}_+\) operator on the fractional stable set polytope to compute the … Read more
We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more
In the known Interval Scheduling problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval and each job has a specic time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We … Read more