Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Polynomial-Time Approximation Schemes for Circle and Other Packing Problems

Texto completo
Autor(es):
Miyazawa, Flavio K. ; Pedrosa, Lehilton L. C. ; Schouery, Rafael C. S. ; Sviridenko, Maxim ; Wakabayashi, Yoshiko
Número total de Autores: 5
Tipo de documento: Artigo Científico
Fonte: ALGORITHMICA; v. 76, n. 2, p. 536-568, OCT 2016.
Citações Web of Science: 5
Resumo

We consider the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height , for some arbitrarily small number . For this problem, we obtain an asymptotic approximation scheme (APTAS) that is polynomial on , and thus may be given as part of the problem input. For the special case that is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height using no more than the number of bins in an optimal packing without resource augmentation. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. Our algorithms are the first approximation schemes for circle packing problems, and are based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTAS's for the problems of packing d-dimensional spheres into hypercubes under the L-p-norm. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 13/02434-8 - Problemas de otimização combinatória: problemas de empacotamento e correlatos
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Pesquisador Visitante - Internacional
Processo FAPESP: 10/20710-4 - Algoritmos de aproximação para problemas de localização com diferentes funções de distância
Beneficiário:Lehilton Lelis Chaves Pedrosa
Linha de fomento: Bolsas no Brasil - Doutorado
Processo FAPESP: 13/21744-8 - Abordagens teóricas e práticas para problemas de empacotamento
Beneficiário:Rafael Crivellari Saliba Schouery
Linha de fomento: Bolsas no Brasil - Pós-Doutorado