Techniques and results on approximation algorithms for packing circles

被引:0
|
作者
Flávio K. Miyazawa
Yoshiko Wakabayashi
机构
[1] University of Campinas,Institute of Computing
[2] University of São Paulo,Institute of Mathematics and Statistics
来源
São Paulo Journal of Mathematical Sciences | 2022年 / 16卷
关键词
Circle packing; Approximation; Bin packing; Strip packing; Knapsack; 68W25; 68W27; 68Q17; 52C17; 52C26;
D O I
暂无
中图分类号
学科分类号
摘要
This survey provides an introductory guide to some techniques used in the design of approximation algorithms for circle packing problems. We address three such packing problems, in which the circles may have different sizes. They differ on the type of the recipient. We consider the classical bin packing and strip packing, and a variant called knapsack packing. Our aim is to discuss some techniques and basic algorithms to motivate the reader to investigate these and other related problems. We also present the ideas used on more elaborated algorithms, without going into details, and mention known results on these problems.
引用
收藏
页码:585 / 615
页数:30
相关论文
共 50 条
  • [11] Linear time-approximation algorithms for bin packing
    Zhang, GC
    Cai, XQ
    Wong, CK
    OPERATIONS RESEARCH LETTERS, 2000, 26 (05) : 217 - 222
  • [12] Approximation algorithms for the integrated path and bin packing problem
    Li, Weidong
    Sun, Ruiqing
    RAIRO-OPERATIONS RESEARCH, 2025, 59 (01) : 325 - 333
  • [13] Packing circles and spheres on surfaces
    Schiftner, Alexander
    Hoebinger, Mathias
    Wallner, Johannes
    Pottmann, Helmut
    ACM TRANSACTIONS ON GRAPHICS, 2009, 28 (05): : 1 - 8
  • [14] APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS
    Bougeret, Marin
    Dutot, Pierre-Francois
    Jansen, Klaus
    Robenek, Christina
    Trystram, Denis
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2011, 3 (04) : 553 - 586
  • [15] A NOTE ON DUAL APPROXIMATION ALGORITHMS FOR CLASS CONSTRAINED BIN PACKING PROBLEMS
    Xavier, Eduardo C.
    Miyazawa, Flavio Keidi
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2009, 43 (02): : 239 - 248
  • [16] Bin packing in multiple dimensions: Inapproximability results and approximation schemes
    Bansal, N
    Correa, JR
    Kenyon, C
    Sviridenko, M
    MATHEMATICS OF OPERATIONS RESEARCH, 2006, 31 (01) : 31 - 49
  • [17] On packing density of growing size circles
    Laszlo, Lajos
    ACTA UNIVERSITATIS SAPIENTIAE-MATHEMATICA, 2016, 8 (02) : 249 - 254
  • [18] Patterns and pathways of packing circles into a square
    Au, Chikit
    INTERNATIONAL JOURNAL OF COMPUTER APPLICATIONS IN TECHNOLOGY, 2013, 48 (01) : 58 - 73
  • [19] Tight partitions for packing circles in a circle
    Ekanayake, Dinesh B.
    Lafountain, Douglas J.
    ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2024, (51): : 115 - 136
  • [20] Apollonian Packing of Circles within Ellipses
    Santini, Carlo
    Mangini, Fabio
    Frezza, Fabrizio
    ALGORITHMS, 2023, 16 (03)