10 citations · 11 across the 10 of their papers we have counts for
11 papers
On the power of counting the total number of computation paths of NPTMs
Eleni Bakali, Aggeliki Chalki, Sotiris Kanellopoulos +2
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 th…
On the Approximability of External-Influence-Driven Problems
Panagiotis Aivasiliotis, Aris Pagourtzis
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 n…
Approximating Subset Sum Ratio via Partition Computations
Giannis Alonistiotis, Antonis Antonopoulos, Nikolaos Melissinos +3
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 as possi…
Faster Algorithms for -Subset Sum and Variations
Antonis Antonopoulos, Aris Pagourtzis, Stavros Petsalakis +1
We present new, faster pseudopolynomial time algorithms for the -Subset Sum problem, defined as follows: given a set of positive integers and targets $t_1, \ldots, t…
Approximation Schemes for Subset Sum Ratio Problems
Nikolaos Melissinos, Aris Pagourtzis, Theofilos Triommatis
We consider the Subset Sum Ratio Problem (), 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, a…
Characterizations and approximability of hard counting classes below #P
Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis
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…
Approximate #Knapsack Computations to Count Semi-Fair Allocations
Theofilos Triommatis, Aris Pagourtzis
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 pro…
Parameterized Fine-Grained Reductions
Elli Anastasiadi, Antonis Antonopoulos, Aris Pagourtzis +1
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. T…
A Faster FPTAS for the Subset-Sums Ratio Problem
Nikolaos Melissinos, Aris Pagourtzis
The Subset-Sums Ratio problem (SSR) is an optimization problem 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…
Joining Local Knowledge to Communicate Reliably (Extended Abstract)
Aris Pagourtzis, Giorgos Panagiotakos, Dimitris Sakavalas
A fundamental primitive in distributed computing is Reliable Message Transmission (RMT), which refers to the task of correctly sending a message from a party (or player) to another…
-shot Broadcasting in Ad Hoc Radio Networks
Sushanta Karmakar, Paraschos Koutris, Aris Pagourtzis +1
We study distributed broadcasting protocols with few transmissions (`shots') in radio networks where the topology is unknown. In particular, we examine the case in which a bound $k…