Automatically assigned DDC number: 004015114
Manually assigned DDC number: 00631

Number of references: 4

Title: Parallel Searching on m Rays

Author:

Author:

Author:

Subject: Mikael Hammar,Bengt J. Nilsson,Sven Schuierer Parallel Searching on m Rays

Description: In this paper we investigate parallel searching on m concurrent rays. We assume that a target t is located somewhere on one of the rays and that a group of m point robots has to reach t. Furthermore, we assume that the robots have no way of communicating over distance. Given a strategy S we are interested in the competitive ratio which is defined as the ratio of the time needed by the robots using S and the time needed if the location of t is known in advance. If a lower bound on the distance to the target is known, then there is a simple strategy which achieves a competitive ratio of 9 --- independent of m. We show that even in the case m = 2 there is a lower bound of 9 on the competitive ratio for two large classes of strategies. Moreover, we show that a lower bound of 9 for m = 2 implies a lower bound of 9 for m ? 2 --- as is to be expected. If the minimum distance to the target is not known in advance, then we show a lower bound on the competitive ratio of 1 + 2(k + 1) k+1 =k k...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1998-07-02

Format: ps

Identifier: http://citeseer.ist.psu.edu/147566.html

Source: http://www.dna.lth.se/Research/Algorithms/Papers/bengt7.ps

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml version="1.0" encoding="UTF-8"?>

<references_metadata>

<rec ID="/80651.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="Piecemeal Learning of an Unknown Environment,">

<identifier Org="ISBN:0818643706" Paper_ID="/80651.html" Extracted="0818643706" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0818665823" Paper_ID="/80651.html" Extracted="0818665823" />

<identifier Org="ISBN:0897916115" Paper_ID="/80651.html" Extracted="0897916115" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0897917235" Paper_ID="/80651.html" Extracted="0897917235" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0898713552" Paper_ID="/80651.html" Extracted="0898713552" DDC="519.4/0285/51" Normalized_DDC="5194028551" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0898714109" Paper_ID="/80651.html" Extracted="0898714109" />

<identifier Org="ISBN:0898714907" Paper_ID="/80651.html" Extracted="0898714907" />

<identifier Org="ISBN:1584886234" Paper_ID="/80651.html" Extracted="1584886234" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540212361" Paper_ID="/80651.html" Extracted="3540212361" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540212582" Paper_ID="/80651.html" Extracted="3540212582" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540424709" Paper_ID="/80651.html" Extracted="3540424709" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540438661" Paper_ID="/80651.html" Extracted="3540438661" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540441808" Paper_ID="/80651.html" Extracted="3540441808" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540633073" Paper_ID="/80651.html" Extracted="3540633073" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:354065691X" Paper_ID="/80651.html" Extracted="354065691X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540667318" Paper_ID="/80651.html" Extracted="3540667318" DDC="004.0151" Normalized_DDC="0040151" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:354077095X" Paper_ID="/80651.html" Extracted="354077095X" />

</rec>

<rec ID="/257602.html" Type="inproceedings" CiteSeer_Book="Proceedings of the Tenth Annual Symposium on Computational Geometry" CiteSeer_Volume="" Title="Competitive Searching in a Generalized Street,">

<identifier Org="ISBN:0521568765" Paper_ID="/257602.html" Extracted="0521568765" DDC="629.8/92" Normalized_DDC="629892" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:0521875749" Paper_ID="/257602.html" Extracted="0521875749" DDC="006.37" Normalized_DDC="00637" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:0821842463" Paper_ID="/257602.html" Extracted="0821842463" DDC="629.8/9201514" Normalized_DDC="62989201514" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:0898713498" Paper_ID="/257602.html" Extracted="0898713498" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:1584883014" Paper_ID="/257602.html" Extracted="1584883014" DDC="516/.13" Normalized_DDC="51613" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:354000579X" Paper_ID="/257602.html" Extracted="354000579X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540257284" Paper_ID="/257602.html" Extracted="3540257284" DDC="629.8/92" Normalized_DDC="629892" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540433996" Paper_ID="/257602.html" Extracted="3540433996" DDC="629.8/92" Normalized_DDC="629892" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540438661" Paper_ID="/257602.html" Extracted="3540438661" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540605738" Paper_ID="/257602.html" Extracted="3540605738" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540633073" Paper_ID="/257602.html" Extracted="3540633073" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540633863" Paper_ID="/257602.html" Extracted="3540633863" DDC="004" Normalized_DDC="004" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540648240" Paper_ID="/257602.html" Extracted="3540648240" DDC="004" Normalized_DDC="004" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:354065691X" Paper_ID="/257602.html" Extracted="354065691X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540662790" Paper_ID="/257602.html" Extracted="3540662790" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540684042" Paper_ID="/257602.html" Extracted="3540684042" DDC="629.892" Normalized_DDC="629892" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:9810222386" Paper_ID="/257602.html" Extracted="9810222386" DDC="629.8/92" Normalized_DDC="629892" Normalized_Weight="0.058823529411764705" />

</rec>

<rec ID="/34052.html" Type="inproceedings" CiteSeer_Book="SODA ACMSIAM Symposium on Discrete Algorithms A Conference on Theoretical and Experimental Analysis of Discrete Algorithms" CiteSeer_Volume="" Title="On-Line Search in a Simple Polygon,">

<identifier Org="ISBN:0521875749" Paper_ID="/34052.html" Extracted="0521875749" DDC="006.37" Normalized_DDC="00637" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:0898713293" Paper_ID="/34052.html" Extracted="0898713293" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:0898713498" Paper_ID="/34052.html" Extracted="0898713498" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:1584883014" Paper_ID="/34052.html" Extracted="1584883014" DDC="516/.13" Normalized_DDC="51613" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:354000579X" Paper_ID="/34052.html" Extracted="354000579X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540006222" Paper_ID="/34052.html" Extracted="3540006222" DDC="005.8/2" Normalized_DDC="00582" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540433996" Paper_ID="/34052.html" Extracted="3540433996" DDC="629.8/92" Normalized_DDC="629892" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540438661" Paper_ID="/34052.html" Extracted="3540438661" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540605738" Paper_ID="/34052.html" Extracted="3540605738" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540614222" Paper_ID="/34052.html" Extracted="3540614222" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540620346" Paper_ID="/34052.html" Extracted="3540620346" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540633863" Paper_ID="/34052.html" Extracted="3540633863" DDC="004" Normalized_DDC="004" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:354065691X" Paper_ID="/34052.html" Extracted="354065691X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540662790" Paper_ID="/34052.html" Extracted="3540662790" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540667318" Paper_ID="/34052.html" Extracted="3540667318" DDC="004.0151" Normalized_DDC="0040151" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540695060" Paper_ID="/34052.html" Extracted="3540695060" DDC="004" Normalized_DDC="004" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:9810222386" Paper_ID="/34052.html" Extracted="9810222386" DDC="629.8/92" Normalized_DDC="629892" Normalized_Weight="0.058823529411764705" />

</rec>

<rec ID="/129288.html" Type="inproceedings" CiteSeer_Book="SODA ACMSIAM Symposium on Discrete Algorithms A Conference on Theoretical and Experimental Analysis of Discrete Algorithms" CiteSeer_Volume="" Title="Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem,">

<identifier Org="ISBN:0387301623" Paper_ID="/129288.html" Extracted="0387301623" DDC="518.103" Normalized_DDC="518103" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0521862051" Paper_ID="/129288.html" Extracted="0521862051" DDC="629.8/932" Normalized_DDC="6298932" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0897916638" Paper_ID="/129288.html" Extracted="0897916638" DDC="004.01" Normalized_DDC="00401" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0898713137" Paper_ID="/129288.html" Extracted="0898713137" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0898713293" Paper_ID="/129288.html" Extracted="0898713293" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0898713668" Paper_ID="/129288.html" Extracted="0898713668" />

<identifier Org="ISBN:1581137087" Paper_ID="/129288.html" Extracted="1581137087" />

<identifier Org="ISBN:1584883979" Paper_ID="/129288.html" Extracted="1584883979" DDC="658.5/3/0151" Normalized_DDC="658530151" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540006222" Paper_ID="/129288.html" Extracted="3540006222" DDC="005.8/2" Normalized_DDC="00582" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540259201" Paper_ID="/129288.html" Extracted="3540259201" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:354032755X" Paper_ID="/129288.html" Extracted="354032755X" DDC="004.098" Normalized_DDC="004098" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540438661" Paper_ID="/129288.html" Extracted="3540438661" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540633863" Paper_ID="/129288.html" Extracted="3540633863" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540648240" Paper_ID="/129288.html" Extracted="3540648240" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540662790" Paper_ID="/129288.html" Extracted="3540662790" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />

</rec>

<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Parallel Searching on m Rays">

<identifier Org="ISBN:0792374681" Paper_ID="SELF" Extracted="0792374681" DDC="003" Normalized_DDC="003" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540259201" Paper_ID="SELF" Extracted="3540259201" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.25" />

<identifier Org="ISBN:3540438661" Paper_ID="SELF" Extracted="3540438661" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.25" />

<identifier Org="ISBN:354065691X" Paper_ID="SELF" Extracted="354065691X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.25" />

</rec>

</references_metadata>