This article presents the Multiple Objective Spanning Trees repository – MOST – Project. As the name suggests, the MOST Project intends to maintain a repository of tests for the MOST related problems, mainly addressing real-life situations. MOST is motivated by the scarcity of repositories for the problems in the referred field. This entails difficulty in … Read more
We study the integrated inventory distribution problem which is concerned with multiperiod inventory holding, backlogging, and vehicle routing decisions for a set of customers who receive units of a single item from a depot with infinite supply. We consider an environment in which the demand at each customer is deterministic and relatively small compared to … Read more
Intensity–modulated radiation therapy (IMRT) gives rise to systems of linear inequalities, representing the effects of radiation on the irradiated body. These systems are often infeasible, in which case one settles for an approximate solution, such as an {a,ß}–relaxation, meaning that no more than a percent of the inequalities are violated by no more than ß … Read more
We study cooperative games with supermodular costs. We show that supermodular costs arise in a variety of situations: in particular, we show that the problem of minimizing a linear function over a supermodular polyhedron–a problem that often arises in combinatorial optimization–has supermodular optimal costs. In addition, we examine the computational complexity of the least core … Read more
We consider the problem of maximizing a nondecreasing submodular set function over various constraint structures. Specifically, we explore the performance of the greedy algorithm, and a related variant, the locally greedy algorithm in solving submodular function maximization problems. Most classic results on the greedy algorithm and its variant assume the existence of an optimal polynomial-time … Read more
We investigate the problem of sequencing jobs that have multiple components. Each component of the job needs to be processed independently on a specified machine. We derive approximate algorithms for the problem of scheduling such vector jobs to minimize their total completion time in the deterministic as well as stochastic setting. In particular, we propose … Read more
Recently, a general-purpose local-search heuristic method called Extremal Optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in multiobjective optimization and proposes a new novel elitist multiobjective algorithm, called Multiobjective Extremal Optimization (MOEO). In order to extend EO to solve the multiobjective … Read more
We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets. Our main result is a randomized poly-time algorithm which approximates $V(K_1,…,K_n)$ with multiplicative error $e^n$ and with better rates if the affine dimensions of most of the sets $K_i$ are small.\\ Even such rate is impossible to achieve … Read more
Given a weighted undirected graph $G=(V,E)$, a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of $G$. Arkin, Halld\’orsson … Read more
We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices. Specifically, let $A_1,\ldots,A_m \in \R^{n\times n}$ be symmetric, positive semidefinite matrices, and let $b_1,\ldots,b_m \ge 0$. We show that if there exists a symmetric, positive semidefinite matrix $X$ to the system $A_i \bullet X … Read more