Markov decision processes (MDPs) are powerful tools for decision making in uncertain dynamic environments. However, the solutions of MDPs are of limited practical use due to their sensitivity to distributional model parameters, which are typically unknown and have to be estimated by the decision maker. To counter the detrimental effects of estimation errors, we consider … Read more
We introduce the concept of a Markov risk measure and we use it to formulate risk-averse control problems for two Markov decision models: a finite horizon model and a discounted infinite horizon model. For both models we derive risk-averse dynamic programming equations and a value iteration method. For the infinite horizon problem we also develop … Read more
In this paper, we present an Uzawa-based heuristic that is adapted to some type of stochastic optimal control problems. More precisely, we consider dynamical systems that can be divided into small-scale independent subsystems, though linked through a static almost sure coupling constraint at each time step. This type of problem is common in production/portfolio management … Read more
We consider risk-averse formulations of stochastic linear programs having a structure that is common in real-life applications. Specifically, the optimization problem corresponds to controlling over a certain horizon a system whose dynamics is given by a transition equation depending affinely on an interstage dependent stochastic process. We put in place a rolling-horizon time consistent policy. … Read more
In this paper we present some new, practical, geometric optimization techniques for computing polygon partitions, 1D and 2D point, interval, square and rectangle covers, as well as 1D and 2D interval and rectangle K-centers. All the techniques we present have immediate applications to several cost optimization and facility location problems which are quite common in … Read more
In this paper we consider several facility location problems with applications to cost and social welfare optimization, when the area map is encoded as a binary (0,1) mxn matrix. We present algorithmic solutions for all the problems. Some cases are too particular to be used in practical situations, but they are at least a starting … Read more
In this paper we present several algorithmic techniques for inferring the structure of a company when only a limited amount of information is available. We consider problems with two types of inputs: the number of pairs of employees with a given property and restricted information about the hierarchical structure of the company. We provide dynamic … Read more
In this paper we consider two problems regarding the scheduling of available personnel in order to perform a given quantity of work, which can be arbitrarily decomposed into a sequence of activities. We are interested in schedules which minimize the overall dissatisfaction, where each employee’s dissatisfaction is modeled as a time-dependent linear function. For the … Read more
In this paper I investigate several offline and online data transfer scheduling problems and propose efficient algorithms and techniques for addressing them. In the offline case, I present a novel, heuristic, algorithm for scheduling files with divisible sizes on multiple disjoint paths, in order to maximize the total profit (the problem is equivalent to the … Read more
In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network’s performance and fault tolerance. The main … Read more