Linear programming techniques in online computing

Context

Linear programming has already established itself as a valuable tool in the design and analysis of

online algorithms. Essentially, one aims to use concepts such as duality and complementary slackness

with two main objectives: i) to guide the designer towards the right choice of an algorithm; and ii) to

facilitate the performance evaluation of the algorithm. Typically, parts of the linear program (usually

the rows or columns) are revealed sequentially, as a consequence of the online nature of the input.

Some technical issues involve the maintenance of appropriate dual solutions which, unlike the

offline setting, cannot be determined in an one-shot manner.

Objectives

For this topic, we seek two new applications of linear programming in online computing. The first application

concerns the primal-dual and dual-fitting analysis of online algorithms for generalized scheduling problems.

Namely, we seek alternative analysis techniques which in turn yield improved competitive ratios for generalized

flow time objectives. The second application is related to online searching of a target in a given environment.

More specifically, we investigate the challenges of infinite LP formulations for online searching with turn cost

(i.e., when the mobile searcher incurs significant cost upon changing the direction of searching). It is worth

pointing out that even weak duality is not necessarily upheld in infinite linear programs, which makes the

essence of LP-based arguments particularly challenging.

Results

1. Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems

(by Spyros Angelopoulos, Giorgio Lucarelli and Kim Thang Nguyen).

In this work we study a variety of online scheduling problems on a single processor that can be viewed

as extensions of the well-studied problem of minimizing total weighted flow time. Most previous work

on this class of problems has relied on amortized analysis and the use of complicated potential-function arguments.

In this paper we follow a different approach based on the primal-dual and dual-fitting paradigms. In particular,

we provide a framework of analysis that is derived by duality properties, does not rely on potential functions,

gives insights for new algorithms, is applicable to a variety of scheduling problems, and for some such problems

yields improved competitive ratios.

Our approach here is as follows: We begin with an interpretation of a simple greedy algorithm (namely

Highest-Density-First or HDF ) as a primal-dual algorithm, and a corresponding proof that HDF is optimal

for total weighted fractional flow time, which directly implies that it is scalable for the integral objective.

Building upon the salient ideas of the proof, we show how to apply and extend this analysis to several other

problems with more complicated objectives; namely for problems in which we seek to minimize total weighted

functions of flow time. Such functions may not necessarily be linear. This class of problems was first introduced

and studied by Im et al [SIAM J. Comp. 2015]. In certain cases (e.g., concave functions), we obtain improved results;

in others, we obtain a more intuitive analysis that does mot rely to potential functions.

This work appeared in the Proceedings of European Symposium on Algorithms (ESA) 2015.

2. Infinite linear programming and online searching with turn cost.

(by Spyros Angelopoulos, Diogo Aresnio and Christoph Dürr ).

We consider the problem of searching for a hidden target in an environment that consists of a set of concurrent

rays. Every time the searcher turns direction, it incurs a fixed cost. The objective is to derive a search strategy

for locating the target as efficiently as possible, and the performance of the strategy is evaluated by means

of the well-established competitive ratio. In this paper we revisit an approach due to Demaine et al [TCS 2006]

based on infinite linear-programming formulations of this problem. We first demonstrate that their definition

of duality in infinite LPs can lead to erroneous results (in that one can obtain dual solutions of higher objective

than the objective of the primal solution). We then provide a non-trivial correction which establishes the optimality

of a certain round-robin search strategy.

This work is currently under review for Theoretical Computer Science.

3. Multiprocessor Search and Scheduling Problems with Setup Cost.

(by Spyros Angelopoulos, Diogo Aresnio, Christoph Dürr and Alejandro Lopez-Ortiz).

In this work we study two optimization problems in a multiprocessor environment in the presence of set-up costs.

The first problem involves online searching with multiple parallel searchers (e.g., robots) that must locate a target

which lies in one of many concurrent rays, and at an unknown position from their common origin. Every time a

searcher turns direction, it incurs a turn cost. The objective is to derive a search strategy for locating the target as

efficiently as possible. The second problem involves contract algorithms, namely algorithms in which the available

computation time is specified prior to their execution. In particular, we seek a schedule of executions of contract

algorithms for several different problems in identical parallel processors so as to efficiently simulate an interruptible

algorithm, assuming that each execution incurs a given set-up cost. Here, an interruptible algorithm is an algorithm

that performs well even without knowing when exactly the interruption will occur. The performance of the search

and scheduling strategies are evaluated by means of well-established measures, namely the competitive ratio and

the acceleration ratio, respectively.

In this paper we provide near-optimal strategies for the above problems, using an approach based on infinite

linear-programming formulations. More precisely, we present a search strategy (resp. schedule) which is optimal

when the number of rays (resp. problems) is a multiple of the number of searchers (resp. processors). For the general

case, we show that the corresponding solutions are very close to optimal.

This work is currently under review for Theory of Computing Systems.