On-line parallel heuristics, processor scheduling and robot searching under the competitive framework

DOI10.1016/J.TCS.2003.08.001MaRDI QIDQ1884992zbMATHOpenAlexFDO

Authors Alejandro Lopez-Ortiz, Sven Schuierer

Publication date 27 October 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2003.08.001

zbMATH Keywords

SchedulingCompetitive ratioOn-line searchingContract algorithmsHeuristic scheduling

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Searching and sorting (68P10) Artificial intelligence for robotics (68T40) Machine vision and scene understanding (68T45)

Recommendations

• Online Parallel Heuristics and Robot Searching under the Competitive Framework
• Parallel searching on \(m\) rays
• Parallel searching in the plane
• The ultimate strategy to search on \(m\) rays?
• Search on a line with faulty robots

Cites work

• scientific article; zbMATH DE number 1003269 (Why is no real title available?)
• scientific article; zbMATH DE number 437569 (Why is no real title available?)
• scientific article; zbMATH DE number 1003229 (Why is no real title available?)
• Competitive searching in polygons—Beyond generalised streets
• Efficient strategies for robot navigation in unknown environment
• Generalized streets revisited
• Lower bounds in on-line geometric searching
• Parallel searching in the plane
• Search games
• Searching in the plane
• The ultimate strategy to search on \(m\) rays?
• Walking an unknown street with bounded detour

Cited in

(20)

• Online algorithms for searching and exploration in the plane
• Parallel online algorithms for the bin packing problem
• Further connections between contract-scheduling and ray-searching problems
• Weighted online search
• Online search with a hint
• Two-agent tree evacuation
• Multi-processor search and scheduling problems with setup cost
• Ranking hypotheses to minimize the search cost in probabilistic inference models
• Competitive search in a network
• Online Parallel Heuristics and Robot Searching under the Competitive Framework
• Graph exploration by a finite automaton
• Best-of-both-worlds analysis of online search
• Multi-target ray searching problems
• Optimal Constructions of Hybrid Algorithms
• Infinite linear programming and online searching with turn cost
• scientific article; zbMATH DE number 7559116 (Why is no real title available?)
• Multi-target ray searching problems
• Search games: a review
• The expanding search ratio of a graph
• Wireless evacuation on \(m\) rays with \(k\) searchers

This page was built for publication: On-line parallel heuristics, processor scheduling and robot searching under the competitive framework

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1884992)