EDBT 2026 Demo / reviewers in the wild / expert
Tzvi Alon
dblp:190/7672
· DBLP profile ↗
3ranked-venue papers
3as first author
3since 2021 · last 2022
0000-0002-3847-8005ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 3 · 3 first-author · 3 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2022 | Strongly Polynomial FPTASes for Monotone Dynamic Programs
Tzvi Alon, Nir Halman |
Algorithmica | 1 |
| 2021 | A faster FPTAS for counting two-rowed contingency tables
Tzvi Alon, Nir Halman |
Discret. Appl. Math. | 1 |
| 2021 | Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made EasierabstractIn this paper we go one step further in the automatic generation of FPTASes for multistage stochastic dynamic programs with scalar state and action spaces, in which the cost-to-go functions have a monotone structure in the state variable. While there exist a few frameworks for automatic generation of FPTASes, so far none of them is general and simple enough to be extensively used. We believe that our framework has these two attributes and has great potential to attract interest from both the operations research and theoretical computer science communities. Moreover, it seems very reasonable that many intractable problems that currently do not admit an FPTAS, can be formulated as DPs that fit into our framework and therefore will admit a first FPTAS. Our results are achieved by a combination of Bellman equation formulations, the technique of $K$-approximation sets and functions, and in particular the calculus of $K$-approximation functions. Tzvi Alon, Nir Halman |
SIAM J. Discret. Math. | 1 |