In this paper we introduce novel algorithmic strategies for effciently playing two-player games in which the players have different or identical player roles. In the case of identical roles, the players compete for the same objective (that of winning
the game). The case with different player roles assumes that one of the players asks questions in order to identify a secret pattern and the other one answers them. The purpose of the first player is to ask as few questions as possible (or that the questions and their number satisfy some previously known constraints) and the purpose of the secret player is to answer the questions in a way that will maximize the number of questions asked by the first player (or in a way which forces the first player to break the constraints of the game). We consider both previously known games (or extensions of theirs) and new types of games, introduced in this paper.
In this paper we present new algorithmic solutions for several constrained geometric server placement problems. We consider the problems of computing the 1-center and obnoxious 1-center of a set of line segments, constrained to lie on a line segment,
and the problem of computing the K-median of a set of points, constrained to lie on a line. The presented algorithms have applications in many types of distributed systems, as well as in various fields which make use of distributed systems for running some of their applications (like chemistry, metallurgy, physics, etc.).
In this paper we present novel algorithmic techniques with a O(H(N)+N/H(N)) time complexity for performing several types of queries and updates on general rooted trees, binary search trees and lists of size N. For rooted trees we introduce a new comp
ressed super-node tree representation which can be used for efficiently addressing a wide range of applications. For binary search trees we discuss the idea of globally rebuilding the entire tree in a fully balanced manner whenever the height of the tree exceeds the value of a conveniently chosen function of the number of tree nodes. In the end of the paper we introduce the H-list data structure which supports concatenation, split and several types of queries. Note that when choosing H(N)=sqrt(N) we obtain O(H(N)+N/H(N))=O(sqrt(N)).
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 t
oo particular to be used in practical situations, but they are at least a starting point for more generic solutions.
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 employees dissatisfaction is modeled as a time-dependent linear function. For the two situations considered we provide a detailed mathematical analysis, as well as efficient algorithms for determining optimal schedules.
In 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.
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 prop
erty and restricted information about the hierarchical structure of the company. We provide dynamic programming and greedy algorithms for these problems.
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 divis
ible sizes on multiple disjoint paths, in order to maximize the total profit (the problem is equivalent to the multiple knapsack problem with divisible item sizes). I then consider a cost optimization problem for transferring a sequence of identical files, subject to time constraints imposed by the data transfer providers. For the online case I propose an algorithmic framework based on the block partitioning method, which can speed up the process of resource allocation and reservation.
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 r
elevant for assessing network reliability and improving the networks performance and fault tolerance. The main technique considered in this paper is dynamic programming.
In this paper we present novel algorithms for several multidimensional data processing problems. We consider problems related to the computation of restricted clusters and of the diameter of a set of points using a new distance function. We also cons
ider two string (1D data) processing problems, regarding an optimal encoding method and the computation of the number of occurrences of a substring within a string generated by a grammar. The algorithms have been thoroughly analyzed from a theoretical point of view and some of them have also been evaluated experimentally.
