Multi-processor Search and Scheduling Problems with Setup Cost

Spyros Angelopoulos, Diogo Arsénio, Christoph Dürr, Alejandro López-Ortiz

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)637-670
Number of pages34
JournalTheory of Computing Systems
Volume60
Issue number4
DOIs
StatePublished - May 1 2017

Keywords

  • Anytime algorithms
  • Linear programming
  • Online search
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Multi-processor Search and Scheduling Problems with Setup Cost'. Together they form a unique fingerprint.

Cite this