Efficient Algorithmic Techniques for Several Multidimensional Geometric Data Management and Analysis Problems

this paper I present several novel, efficient, algorithmic techniques for solving some multidimensional geometric data management and analysis problems. The techniques are based on several data structures from computational geometry (e.g. segment tree and range tree) and on the well-known sweep-line method. Citation Proceedings of the 3rd International Conference “Knowledge Management – Projects, Systems and … Read more

Optimal Geometric Partitions, Covers and K-Centers

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

Locating Restricted Facilities on Binary Maps

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

Inferring Company Structure from Limited Available Information

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

Minimum Dissatisfaction Personnel Scheduling

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

Optimal Scheduling of File Transfers with Divisible Sizes on Multiple Disjoint Paths

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

A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth

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