In this work we investigate the min-max-min robust optimization problem for binary problems with uncertain cost-vectors. The idea of the approach is to calculate a set of k feasible solutions which are worst-case optimal if in each possible scenario the best of the k solutions is implemented. It is known that the min-max-min robust problem … Read more
\(\) We consider two-stage robust linear programs with a budget of uncertainty for the righthand side. In this scenario set, which is frequently used in robust optimization, the uncertain righthand side for each row lies in an interval and the relative increases summed over all rows are less than a budget \(\Gamma\). We develop a … Read more
One popular approach to access the importance/influence of a group of nodes in a network is based on the notion of centrality. For a given group, its group betweenness centrality is computed, first, by evaluating a ratio of shortest paths between each node pair in a network that are “covered” by at least one node … Read more
We consider the temporal bin packing problem with fire-ups (TBPP-FU), a branch of operations research recently introduced in multi-objective cloud computing. In this scenario, any item is equipped with a resource demand and a lifespan meaning that it requires the bin capacity only during that time interval. We then aim at finding a schedule minimizing … Read more
\(\) The question of finding the largest integer contained between two given lists of integers is trivial when integer ordering is interpreted in its usual way. We propose a nontrivial variant wherein each ordering comparison is performed after integers have been mapped under some bijection, and analyze the computational complexity of our combinatorial problem under … Read more
Motivated by applications in e-commerce logistics where orders or items arrive at different times and must be dispatched or processed in batches, we propose the submodular dispatching problem (SMD), a strongly NP-hard model defined by a set of orders with release times and a non-decreasing submodular dispatch time function. A single uncapacitated vehicle must dispatch … Read more
We investigate the optimal piecewise linear approximation of the bivariate product $ xy $ over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the approximation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using … Read more
We study a two-stage, finite-scenarios stochastic version of the set multicover problem, where there is uncertainty about a demand for each element to be covered and the penalty cost is imposed linearly on the shortfall in each demand. This problem is NP-hard and has an application in shift scheduling in crowdsourced delivery services. For this … Read more
De Klerk and Pasechnik (2002) introduced the bounds $\vartheta^{(r)}(G)$ ($r\in \mathbb{N}$) for the stability number $\alpha(G)$ of a graph $G$ and conjectured exactness at order $\alpha(G)-1$: $\vartheta^{(\alpha(G)-1)}(G)=\alpha(G)$. These bounds rely on the conic approximations $\mathcal{K}_n^{(r)}$ by Parrilo (2000) for the copositive cone $\text{COP}_n$. A difficulty in the convergence analysis of $\vartheta^{(r)}$ is the bad behaviour … Read more
We consider the problem of laying out several objects in an equal number of pre-defined positions. Objects are allowed finitely many orientations, can overlap each other, and must be arranged contiguously. We are particularly interested in the case when the evaluation of the dimensions of the objects requires computational or physical effort. We develop a … Read more