7 papers
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…