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>

www.000webhost.com