Dispersing points on intervals

DOI10.1016/j.dam.2017.12.028zbMath1410.68372OpenAlexW2783443149MaRDI QIDQ1706121

Shimin Li, Haitao Wang

Publication date: 21 March 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6824/

zbMATH Keywords

intervalscycleslinesdispersing points

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

The dispersive art gallery problem, Dispersing and grouping points on planar segments

Cites Work

• Unnamed Item
• Unnamed Item
• Minimizing maximum lateness of jobs with naturally bounded job data on a single machine in polynomial time
• A study of single-machine scheduling problem to maximize throughput
• The densest packing of equal circles into a parallel strip
• A note on scheduling equal-length jobs to maximize throughput
• The discrete p-dispersion problem
• The equitable dispersion problem
• A study on two geometric location problems
• Optimal packing and covering in the plane are NP-complete
• Scheduling of unit-length independent tasks with execution constraints
• New results in the packing of equal circles in a square
• Connectivity graphs of uncertainty regions
• Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines
• Heuristic and Special Case Algorithms for Dispersion Problems
• A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
• Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help
• Solving Generalized Maximum Dispersion with Linear Programming
• Approximation of geometric dispersion problems