| bibtype |
J -
Journal Article
|
| ARLID |
0575483 |
| utime |
20240402214417.0 |
| mtime |
20230914235959.9 |
| SCOPUS |
85151044921 |
| WOS |
001027998000026 |
| DOI |
10.1038/s41598-023-31786-3 |
| title
(primary) (eng) |
Bounded Wang tilings with integer programming and graph-based heuristics |
| specification |
| page_count |
22 s. |
| media_type |
E |
|
| serial |
| ARLID |
cav_un_epca*0386594 |
| ISSN |
2045-2322 |
| title
|
Scientific Reports |
| volume_id |
13 |
| publisher |
| name |
Nature Publishing Group |
|
|
| keyword |
integer programming |
| keyword |
combinatorial optimization |
| keyword |
bounded Wang tiling |
| keyword |
heuristics |
| keyword |
graph theory |
| author
(primary) |
| ARLID |
cav_un_auth*0454762 |
| name1 |
Tyburec |
| name2 |
Marek |
| institution |
UTIA-B |
| full_dept (cz) |
Matematická teorie rozhodování |
| full_dept (eng) |
Department of Decision Making Theory |
| department (cz) |
MTR |
| department (eng) |
MTR |
| country |
CZ |
| fullinstit |
Ústav teorie informace a automatizace AV ČR, v. v. i. |
|
| author
|
| ARLID |
cav_un_auth*0018366 |
| name1 |
Zeman |
| name2 |
J. |
| country |
CZ |
|
| source |
|
| source |
|
| cas_special |
| project |
| project_id |
GX19-26143X |
| agency |
GA ČR |
| country |
CZ |
| ARLID |
cav_un_auth*0440774 |
|
| abstract
(eng) |
Wang tiles enable efficient pattern compression while avoiding the periodicity in tile distribution via programmable matching rules. However, most research in Wang tilings has considered tiling the infinite plane. Motivated by emerging applications in materials engineering, we consider the bounded version of the tiling problem and offer four integer programming formulations to construct valid or nearly-valid Wang tilings: a decision, maximum-rectangular tiling, maximum cover, and maximum adjacency constraint satisfaction formulations. To facilitate a finer control over the resulting tilings, we extend these programs with tile-based, color-based, packing, and variable-sized periodic constraints. Furthermore, we introduce an efficient heuristic algorithm for the maximum-cover variant based on the shortest path search in directed acyclic graphs and derive simple modifications to provide a 1/2 approximation guarantee for arbitrary tile sets, and a 2/3 guarantee for tile sets with cyclic transducers. Finally, we benchmark the performance of the integer programming formulations and of the heuristic algorithms showing that the heuristics provide very competitive outputs in a fraction of time. As a by-product, we reveal errors in two well-known aperiodic tile sets: the Knuth tile set contains a tile unusable in two-way infinite tilings, and the Lagae corner tile set is not aperiodic. |
| result_subspec |
WOS |
| RIV |
BA |
| FORD0 |
10000 |
| FORD1 |
10100 |
| FORD2 |
10102 |
| reportyear |
2024 |
| num_of_auth |
2 |
| inst_support |
RVO:67985556 |
| permalink |
https://hdl.handle.net/11104/0345382 |
| cooperation |
| ARLID |
cav_un_auth*0357942 |
| name |
ČVUT, Fakulta stavební |
| country |
CZ |
|
| confidential |
S |
| article_num |
4865 |
| mrcbC91 |
A |
| mrcbT16-e |
MULTIDISCIPLINARYSCIENCES |
| mrcbT16-j |
1.061 |
| mrcbT16-s |
0.9 |
| mrcbT16-D |
Q2 |
| mrcbT16-E |
Q2 |
| arlyear |
2023 |
| mrcbU14 |
85151044921 SCOPUS |
| mrcbU24 |
PUBMED |
| mrcbU34 |
001027998000026 WOS |
| mrcbU63 |
cav_un_epca*0386594 Scientific Reports Roč. 13 1 2023 2045-2322 2045-2322 Nature Publishing Group |
|