1 citations · 1 across the 4 of their papers we have counts for
9 papers
Subexponential Algorithm for High Multiplicity Fair Division of Mixed Instances via Stereometry
Yuriy Dementiev, Fedor Pribytkov, Danil Sagunov
We study the problem of computing an envy-free (EF) allocation of indivisible items among agents when items come in three distinct types. Each agent holds additive valuatio…
Exploiting Spanning Trees for Directed Acyclicity
Sergei Khargeliia, Danil Sagunov
We study the weighted case of the \textsc{Maximum Acyclic Subgraph (MAS)} problem, where each edge of a given directed graph has a positive weight assigned, and the task is to find…
Learning Augmented Exact Exponential Algorithms
Tatiana Belova, Yuriy Dementiev, Danil Sagunov
The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, th…
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
Fedor V. Fomin, Petr A. Golovach, Nikola JedliÄková +3
The classic theorem of Gallai and Milgram (1960) generalizes several fundamental results in Graph Theory, such as Dilworth's theorem on posets and KÅnig's theorem on matchings in…
Structural Approach to Guiding a Present-Biased Agent
Tatiana Belova, Yuriy Dementiev, Artur Ignatiev +1
Time-inconsistent behavior, such as procrastination or abandonment of long-term goals, arises when agents evaluate immediate outcomes disproportionately higher than future ones. Th…
EFX and PO Allocation Exists for Two Types of Goods
Vladimir Davidiuk, Yuriy Dementiev, Artur Ignatiev +1
We study the problem of fairly and efficiently allocating indivisible goods among agents with additive valuations. We focus on envy-freeness up to any good (EFX) -- an important fa…