Data-Collection for the Sloan Digital Sky Survey: a Network-Flow Heuristic

Details Data-Collection for the Sloan Digital Sky Survey: a Network-Flow Heuristic Data-Collection for the Sloan Digital Sky Survey: a Network-Flow Heuristic

2002-05-18

arxiv.org/abs/cs/0205034v1

Journal of Algorithms 27(2):339-356 (1998)

Computer Science

Data Structures and Algorithms

proceedings version appeared in ACM-SIAM Symposium on Discrete Algorithms (1998)

Scientific paper

The goal of the Sloan Digital Sky Survey is ``to map in detail one-quarter of the entire sky, determining the positions and absolute brightnesses of more than 100 million celestial objects''. The survey will be performed by taking ``snapshots'' through a large telescope. Each snapshot can capture up to 600 objects from a small circle of the sky. This paper describes the design and implementation of the algorithm that is being used to determine the snapshots so as to minimize their number. The problem is NP-hard in general; the algorithm described is a heuristic, based on Lagriangian-relaxation and min-cost network flow. It gets within 5-15% of a naive lower bound, whereas using a ``uniform'' cover only gets within 25-35%.

Affiliated with

Also associated with

No associations

Rating

Data-Collection for the Sloan Digital Sky Survey: a Network-Flow Heuristic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Data-Collection for the Sloan Digital Sky Survey: a Network-Flow Heuristic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data-Collection for the Sloan Digital Sky Survey: a Network-Flow Heuristic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599130