Keyword: NP-hard

Found 42 papers in total
GRASP with path relinking for the orienteering problem
GRASP with path relinking for the orienteering problem
2014,
In this paper, we address an optimization problem resulting from the combination of...
A taxonomy of line balancing problems and their solutionapproaches
A taxonomy of line balancing problems and their solutionapproaches
2013,
Line balancing belongs to a class of intensively studied combinatorial optimization...
Computing Optimal Steiner Trees in Polynomial Space
Computing Optimal Steiner Trees in Polynomial Space
2013,
Given an n ‐node edge‐weighted graph and a subset of k terminal nodes,...
Complexity of Buffer Capacity Allocation Problems for Production Lines with Unreliable Machines
Complexity of Buffer Capacity Allocation Problems for Production Lines with Unreliable Machines
2013,
Buffer capacity allocation problems for flow‐line manufacturing systems with...
A polynomial case of the cardinality‐constrained quadratic optimization problem
A polynomial case of the cardinality‐constrained quadratic optimization problem
2013,
We propose in this paper a fixed parameter polynomial algorithm for the...
Car sequencing is NP‐hard: a short proof
Car sequencing is NP‐hard: a short proof
2013,
In this note, a new proof is given that the car sequencing (CS) problem is...
The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders
The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders
2013,
Comparing and ranking information is an important topic in social and information...
Non‐preemptive speed scaling
Non‐preemptive speed scaling
2013,
We consider the following offline variant of the speed scaling problem introduced by...
Bounded parallel‐batching scheduling with two competing agents
Bounded parallel‐batching scheduling with two competing agents
2013,
We consider a scheduling problem in which two agents, each with a set of...
Outsourcing and scheduling for two‐machine ordered flow shop scheduling problems
Outsourcing and scheduling for two‐machine ordered flow shop scheduling problems
2013,
This paper considers a two‐machine ordered flow shop problem, where each job is...
Weighted inverse maximum perfect matching problems under the Hamming distance
Weighted inverse maximum perfect matching problems under the Hamming distance
2013,
Given an undirected network G ( V , E , c ) and a perfect matching M 0 , the inverse...
An adaptive search for the response time variability problem☆
An adaptive search for the response time variability problem☆
2012,
The Response Time Variability Problem (RTVP) is an NP‐hard combinatorial...
Approximation and Tidying–A Problem Kernel for s‐Plex Cluster Vertex Deletion
Approximation and Tidying–A Problem Kernel for s‐Plex Cluster Vertex Deletion
2012,
We introduce the NP‐hard graph‐based data clustering problem s ‐...
Approximation Schemes for Packing Splittable Items with Cardinality Constraints
Approximation Schemes for Packing Splittable Items with Cardinality Constraints
2012,
We continue the study of bin packing with splittable items and cardinality...
Drawing (Complete) Binary Tanglegrams
Drawing (Complete) Binary Tanglegrams
2012,
A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are...
The Parameterized Complexity of Stabbing Rectangles
The Parameterized Complexity of Stabbing Rectangles
2012,
The NP‐complete geometric covering problem Rectangle Stabbing is defined as...
On a constant factor approximation for minmax regret problems using a symmetry point scenario
On a constant factor approximation for minmax regret problems using a symmetry point scenario
2012,
In order to find a robust solution under an unknown linear cost function it will be...
An Exact Exponential Time Algorithm for Power Dominating Set
An Exact Exponential Time Algorithm for Power Dominating Set
2012,
The Power Dominating Set problem is an extension of the well‐known domination...
Improved Approximation Algorithms for Data Migration
Improved Approximation Algorithms for Data Migration
2012,
Our work is motivated by the need to manage data items on a collection of storage...
Computing solutions for matching games
Computing solutions for matching games
2012,
A matching game is a cooperative game ( N , v ) defined on a graph G = ( N , E ) with...
On Two Class‐Constrained Versions of the Multiple Knapsack Problem
On Two Class‐Constrained Versions of the Multiple Knapsack Problem
2001,
We study two variants of the classic knapsack problem, in which we need to place items...
Polynomial Time Approximation Schemes for Some Dense Instances of NP‐Hard Optimization Problems
Polynomial Time Approximation Schemes for Some Dense Instances of NP‐Hard Optimization Problems
2001,
We survey recent results on the existence of polynomial time approximation schemes for...
Best Possible Approximation Algorithm for MAX SAT with Cardinality Constraint
Best Possible Approximation Algorithm for MAX SAT with Cardinality Constraint
2001,
We consider the MAX SAT problem with the additional constraint that at most P...
Further Thoughts on the Syntenic Distance between Genomes
Further Thoughts on the Syntenic Distance between Genomes
2002,
The syntenic distance between two multi-chromosomal genomes is the minimum number of...
Papers per page: