Zobrazeno 1 - 10
of 41
pro vyhledávání: '"Theory of computation ��� Packing and covering problems"'
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3c64c4779bf3854a20cb475ea9207cca
Motivated by recent progress on stochastic matching with few queries, we embark on a systematic study of the sparsification of stochastic packing problems more generally. Specifically, we consider packing problems where elements are independently act
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ac2d6933727c8c498d326eadda4d6a9f
Autor:
Klimm, Max, Knaack, Martin
This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::295c5a8494a84e72066e3d5deafd45ce
http://arxiv.org/abs/2209.09668
http://arxiv.org/abs/2209.09668
We investigate preprocessing for vertex-subset problems on graphs. While the notion of kernelization, originating in parameterized complexity theory, is a formalization of provably effective preprocessing aimed at reducing the total instance size, ou
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::175348f667a6432a945157f63bd854f5
http://arxiv.org/abs/2207.00386
http://arxiv.org/abs/2207.00386
We introduce the problem of finding a set $B$ of $k$ points in $[0,1]^n$ such that the expected cost of the cheapest point in $B$ that dominates a random point from $[0,1]^n$ is minimized. We study the case where the coordinates of the random points
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b4e5513b32590e94e4693e1436ace102
Front Matter, Table of Contents, Preface, Conference Organization
LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 0:i-0:xxii
LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 0:i-0:xxii
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c19753a37740f965274159d7f92b57a5
Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least k vertices is considered long. When k ≤ 3, the problem is pol
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::530516b2f383183c6666631ecb340fce
LIPIcs, Volume 244, ESA 2022, Complete Volume
LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 1-1406
LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 1-1406
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ee4feba6a7425c51d63f41832c606963
https://drops.dagstuhl.de/opus/volltexte/2022/16937/
https://drops.dagstuhl.de/opus/volltexte/2022/16937/
Publikováno v:
Leibniz International Proceedings in Informatics
60:1-60:17
60:1-60:17
The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::35974362963cf8a7bf99b6b1d13abbe7
https://hdl.handle.net/11250/3042293
https://hdl.handle.net/11250/3042293