The approximation algorithms for a class of multiple-choice problem

DOI10.1016/J.TCS.2016.06.038MaRDI QIDQ344788zbMATHOpenAlexFDO

Authors Yin Wang, Yinfeng Xu

Publication date 24 November 2016

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

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

zbMATH Keywords

approximation algorithmcomputational geometrycolor-spanning objectsthe smallest enclosing problem

Mathematics Subject Classification ID

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

Recommendations

• An Approximation Algorithm for the Smallest Color-Spanning Circle Problem
• Approximation algorithms for color spanning diameter
• On some geometric problems of color-spanning sets
• Unit covering in color-spanning set model
• Efficiently approximating color-spanning balls

Cites work

• scientific article; zbMATH DE number 1875422 (Why is no real title available?)
• Bichromatic 2-center of pairs of points
• Computing minimum diameter color-spanning sets
• Computing minimum diameter color-spanning sets is hard
• Fast computation of smallest enclosing circle with center on a query line segment
• Finding minimum area \(k\)-gons
• Iterated nearest neighbors and finding minimal polytopes
• Minimum-diameter covering problems
• On enclosing k points by a circle
• On some geometric problems of color-spanning sets
• On the discrete unit disk cover problem
• Sets with No Empty Convex 7-Gons
• Shortest color-spanning intervals
• Unit covering in color-spanning set model

Cited in

(7)

• Unit covering in color-spanning set model
• Efficiently approximating color-spanning balls
• Expected computations on color spanning sets
• Solving the chromatic cone clustering problem via minimum spanning sphere
• Prudent \(k\)-choice functions: Properties and algorithms
• Expected computations on color spanning sets
• Approximation algorithms for color spanning diameter

This page was built for publication: The approximation algorithms for a class of multiple-choice problem

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