Zobrazeno 1 - 10
of 161
pro vyhledávání: '"Theory of computation ��� Approximation algorithms analysis"'
Autor:
Zachary Friggstad, Chaitanya Swamy
Publikováno v:
Journal of Computer and System Sciences. 126:44-58
We consider the directed minimum latency problem (DirLat), wherein we seek a path P visiting all points (or clients) in a given asymmetric metric starting at a given root node r, so as to minimize the sum of the client waiting times, where the waitin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::65c837e4f8b678a641298ecb7ad7739d
https://doi.org/10.1016/j.jcss.2021.12.001
https://doi.org/10.1016/j.jcss.2021.12.001
Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be sat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b69227b20d04840d835639dc87968d5b
https://theoretics.episciences.org/8967
https://theoretics.episciences.org/8967
Autor:
Qi, Benjamin, Qi, Richard
We analyze the touring regions problem: find a (1+ε)-approximate Euclidean shortest path in d-dimensional space that starts at a given starting point, ends at a given ending point, and visits given regions R₁, R₂, R₃, … , R_n in that order.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::63c0cfc45b78558a5e50642d7a0b205e
Autor:
Karlin, Anna R.
We describe recent joint work with Nathan Klein and Shayan Oveis Gharan showing that for any metric TSP instance, the max entropy algorithm studied by [Anna R. Karlin et al., 2021] returns a solution of expected cost at most 3/2-ε times the cost of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::535fd510a7037826c17b4fd302bf79a3
A factorization of a string S is a partition of w into substrings u_1,… ,u_k such that S = u_1 u_2 ⋯ u_k. Such a partition is called equality-free if no two factors are equal: u_i ≠ u_j, ∀ i,j with i ≠ j. The maximum equality-free factoriza
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::fe177a958e158fec1fc08d7c481e3436
Autor:
Geerts, Floris, Vandevoort, Brecht
LIPIcs, Volume 255, ICDT 2023, Complete Volume
LIPIcs, Vol. 255, 26th International Conference on Database Theory (ICDT 2023), pages 1-466
LIPIcs, Vol. 255, 26th International Conference on Database Theory (ICDT 2023), pages 1-466
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::293fb00994779f2d5c23730505bad861
In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with integer edge weights, a depot, a set of n terminals, and a distance constraint D. The goal is to find a minimum number of tours starting and ending at the depot suc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::24c9c28fb2eafbb23a7177687bf7e1da
Autor:
Bergamaschi, Thiago
The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4734f1607c170270a2c50bb894d9d654
We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-frag
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::607a0d34f3bb02f6a964a3ecf762e28f
We give a classical $1/(qk+1)$-approximation for the maximum eigenvalue of a $k$-sparse fermionic Hamiltonian with strictly $q$-local terms, as well as a $1/(4k+1)$-approximation when the Hamiltonian has both $2$-local and $4$-local terms. More gener
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::04249fff5acfbd9d0d26b90d1d1b864e