10 citations · 11 across the 18 of their papers we have counts for
10 papers · 1 filter
Exact Algorithms for Resource Reallocation Under Budgetary Constraints
Arun Kumar Das, Sandip Das, Sweta Das +2
Efficient resource (re-)allocation is a critical challenge in optimizing productivity and sustainability within multi-party supply networks. In this work, we introduce the \textsc{…
Structural Parameters for Steiner Orientation
Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos +3
We consider the \textsc{Steiner Orientation} problem, where we are given as input a mixed graph and a set of demand pairs , . The goal is to ori…
Parameterized Critical Node Cut Revisited
Dušan Knop, Nikolaos Melissinos, Manolis Vasilakis
We study how to sparsify connectivity in graphs under a tight deletion budget. Given a graph and integers , Critical Node Cut (CNC) asks whether we can delete at mos…
Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos
Imagine we want to split a group of agents into teams in the most \emph{efficient} way, considering that each agent has their own preferences about their teammates. This scenario i…
Exact Algorithms for Distance to Unique Vertex Cover
Foivos Fioravantes, Dušan Knop, Nikolaos Melissinos +2
Horiyama et al. (AAAI 2024) studied the problem of generating graph instances that possess a unique minimum vertex cover under specific conditions. Their approach involved pre-assi…
Bandwidth Parameterized by Cluster Vertex Deletion Number
Tatsuya Gima, Eun Jung Kim, Noleen Köhler +2
Given a graph and an integer , Bandwidth asks whether there exists a bijection from to such that $\max_{\{u, v \} \in E(G)} | π(u) - π(v)…
Parameterized Max Min Feedback Vertex Set
Michael Lampis, Nikolaos Melissinos, Manolis Vasilakis
Given a graph and an integer , Max Min FVS asks whether there exists a minimal set of vertices of size at least whose deletion destroys all cycles. We present several re…
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…
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…
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…