TY - JOUR

T1 - Multi-processor Search and Scheduling Problems with Setup Cost

AU - Angelopoulos, Spyros

AU - Arsénio, Diogo

AU - Dürr, Christoph

AU - López-Ortiz, Alejandro

N1 - Funding Information:
This work was supported by project ANR-11-BS02-0015 "New Techniques in Online Computation" (NeTOC).
Publisher Copyright:
© 2016, Springer Science+Business Media New York.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2017/5/1

Y1 - 2017/5/1

N2 - We study two optimization problems in a multiprocessor environment in the presence of set-up costs. The first problem involves 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. 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.

AB - We study two optimization problems in a multiprocessor environment in the presence of set-up costs. The first problem involves 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. 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.

KW - Anytime algorithms

KW - Linear programming

KW - Online search

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=84975263652&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84975263652&partnerID=8YFLogxK

U2 - 10.1007/s00224-016-9691-3

DO - 10.1007/s00224-016-9691-3

M3 - Article

AN - SCOPUS:84975263652

VL - 60

SP - 637

EP - 670

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -