Search
Search Results
-
NP-Hardness of Some Data Cleaning Problem
AbstractWe prove the NP-hardness of the data cleaning problem under study. One of the data analysis questions reduces to the problem. As a...
-
Complexity of Ice Quiver Mutation Equivalence
We prove
NP-hardness results for determining whether ice quivers are mutation equivalent to quivers with given properties, specifically, determining...
-
NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes
We consider the following 2-clustering problem. Given n points in Euclidean space, partition it into two subsets (clusters) so that the sum of...
-
On the Cardinality Computation Problem for Regular Languages over Symmetric Groups
AbstractRepresentations of regular languages over symmetric groups in the form of finite automata and regular expressions are considered. The
NP -hard... -
NP-Hardness of Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with Constraints on the Cluster Sizes
AbstractWe consider the problem of clustering a finite set of N points in d -dimensional Euclidean space into two clusters minimizing the sum (over...
-
Minimizing the Total Weighted Duration of Courses in a Single Machine Problem with Precedence Constraints
AbstractA single machine scheduling problem with a given partial order of jobs is considered. There are subsets of jobs called courses. It is...
-
Hybrid Evolutionary Algorithm with Optimized Operators for Total Weighted Tardiness Problem
A new evolutionary algorithm with optimal recombination is proposed for the total weighted tardiness problem on the single machine. We solve the...
-
Complexity Issues in Interval Linear Programming
Interval linear programming studies linear programming problems with interval coefficients. Herein, the intervals represent a range of possible...
-
Graph Homomorphism, Monotone Classes and Bounded Pathwidth
Monotone graph classes are those described by some set of forbidden subgraphs, i.e....
-
Counting on Rainbow k-Connections
For an undirected graph imbued with an edge coloring, a rainbow path (resp. proper path) between a pair of vertices corresponds to a simple path in...
-
On the Power of Counting the Total Number of Computation Paths of NPTMs
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...
-
Computational complexity and algorithms for two scheduling problems under linear constraints
This paper considers two different types of scheduling problems under linear constraints. The first is the single-machine scheduling problem with...
-
On the rectangular knapsack problem
A recent paper by Schulze et al. (Math Methods Oper Res 92(1):107–132, 2020) presented the Rectangular Knapsack Problem ( Rkp ) as a crucial subproblem...
-
Embedding Divisor and Semi-Prime Testability in f-Vectors of Polytopes
We obtain computational hardness results for f -vectors of polytopes by exhibiting reductions of the problems DIVISOR and SEMI-PRIME TESTABILITY to...
-
Approximation and Fixed Parameter Algorithms for the Approximate Cover Problem
Amir et al. (CPM 2017) introduce the approximate string cover problem (ACP) motivated by applications including molecular biology, coding, automata...
-
Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths
In a graph, a (perfect) matching cut is an edge cut that is a (perfect) matching. matching cut (mc), respectively, perfect matching cut (pmc), is the...
-
Minimizing the influence spread over a network through node interception
We consider the problem of determining the optimal node interception strategy during influence propagation over a (directed) network
... 
-
Computational Complexity of Two Problems of Cognitive Data Analysis
AbstractThe NP-hardness in the strong sense is proved for two problems of cognitive data analysis. One of them is the problem of taxonomy...
-
Proper colorability of segment intersection graphs
We consider the vertex proper coloring problem for highly restricted instances of geometric intersection graphs of line segments embedded in the...
-
The robust bilevel continuous knapsack problem with uncertain coefficients in the follower’s objective
We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing...
