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.