EDBT 2026 Demo / reviewers in the wild / expert
Vladislav Makarov 0001
dblp:233/4177-1
· DBLP profile ↗
4ranked-venue papers
3as first author
3since 2021 · last 2025
0009-0001-8769-752XORCID · verified
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 3 · 2 first-author · 3 since 2021Applied, interdisciplinary, general and emerging computing · 1 · 1 first-author
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2025 | Checking whether Two Unambiguous Context-Free Grammars Describe the Same Set of Strings of Length n
Vladislav Makarov 0001 |
DLT | 1 |
| 2024 | Partitioning Problems with Splittings and Interval TargetsabstractThe n-way number partitioning problem is a classic problem in combinatorial optimization, with applications to diverse settings such as fair allocation and machine scheduling. All these problems are NP-hard, but various approximation algorithms are known. We consider three closely related kinds of approximations. The first two variants optimize the partition such that: in the first variant some fixed number s of items can be split between two or more bins and in the second variant we allow at most a fixed number t of splittings. The third variant is a decision problem: the largest bin sum must be within a pre-specified interval, parameterized by a fixed rational number u times the largest item size. When the number of bins n is unbounded, we show that every variant is strongly NP-complete. When the number of bins n is fixed, the running time depends on the fixed parameters s,t,u. For each variant, we give a complete picture of its running time. For n = 2, the running time is easy to identify. Our main results consider any fixed integer n ≥ 3. Using a two-way polynomial-time reduction between the first and the third variant, we show that n-way number-partitioning with s split items can be solved in polynomial time if s ≥ n-2, and it is NP-complete otherwise. Also, n-way number-partitioning with t splittings can be solved in polynomial time if t ≥ n-1, and it is NP-complete otherwise. Finally, we show that the third variant can be solved in polynomial time if u ≥ (n-2)/n, and it is NP-complete otherwise. Our positive results for the optimization problems consider both min-max and max-min versions. Using the same reduction, we provide a fully polynomial-time approximation scheme for the case where the number of split items is lower than n-2. Samuel Bismuth, Vladislav Makarov 0001, Erel Segal-Halevi, Dana Shapira |
ISAAC | 2 |
| 2021 | Bounded Languages Described by GF(2)-grammars
Vladislav Makarov 0001 |
DLT | 1 |
| 2019 | On the Expressive Power of GF(2)-Grammars
Vladislav Makarov 0001, Alexander Okhotin |
SOFSEM | 1 |