Zobrazeno 1 - 10
of 122
pro vyhledávání: '"Pagourtzis, Aris"'
In this paper, we define and study variants of several complexity classes of decision problems that are defined via some criteria on the number of accepting paths of an NPTM. In these variants, we modify the acceptance criteria so that they concern t
Externí odkaz:
http://arxiv.org/abs/2306.11614
Domination problems in general can capture situations in which some entities have an effect on other entities (and sometimes on themselves). The usual goal is to select a minimum number of entities that can influence a target group of entities or to
Externí odkaz:
http://arxiv.org/abs/2305.19251
Publikováno v:
In Future Generation Computer Systems February 2025 163
Autor:
Alonistiotis, Giannis, Antonopoulos, Antonis, Melissinos, Nikolaos, Pagourtzis, Aris, Petsalakis, Stavros, Vasilakis, Manolis
We present a new FPTAS for the Subset Sum Ratio problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to $1$ as possible. Our scheme makes use of exact and approximate algorithms for the
Externí odkaz:
http://arxiv.org/abs/2201.04165
We present new, faster pseudopolynomial time algorithms for the $k$-Subset Sum problem, defined as follows: given a set $Z$ of $n$ positive integers and $k$ targets $t_1, \ldots, t_k$, determine whether there exist $k$ disjoint subsets $Z_1,\dots,Z_k
Externí odkaz:
http://arxiv.org/abs/2112.04244
We consider the Subset Sum Ratio Problem ($SSR$), in which given a set of integers the goal is to find two subsets such that the ratio of their sums is as close to~1 as possible, and introduce a family of variations that capture additional meaningful
Externí odkaz:
http://arxiv.org/abs/2003.06622
An important objective of research in counting complexity is to understand which counting problems are approximable. In this quest, the complexity class TotP, a hard subclass of #P, is of key importance, as it contains self-reducible counting problem
Externí odkaz:
http://arxiv.org/abs/2003.02524
In this paper, we study the problem of counting the number of different knapsack solutions with a prescribed cardinality. We present an FPTAS for this problem, based on dynamic programming. We also introduce two different types of semi-fair allocatio
Externí odkaz:
http://arxiv.org/abs/1912.12430
During recent years the field of fine-grained complexity has bloomed to produce a plethora of results, with both applied and theoretical impact on the computer science community. The cornerstone of the framework is the notion of fine-grained reductio
Externí odkaz:
http://arxiv.org/abs/1902.05529
Publikováno v:
In Theoretical Computer Science 4 May 2023 956