Keyword: NP-hard

Found 42 papers in total
Sharp Separation and Applications to Exact and Parameterized Algorithms
Sharp Separation and Applications to Exact and Parameterized Algorithms
2012,
Many divide‐and‐conquer algorithms employ the fact that the vertex set...
On the Approximability of Single‐Machine Scheduling with Precedence Constraints
On the Approximability of Single‐Machine Scheduling with Precedence Constraints
2011,
We consider the single‐machine scheduling problem to minimize the weighted sum...
Matching based very large‐scale neighborhoods for parallel machine scheduling
Matching based very large‐scale neighborhoods for parallel machine scheduling
2011,
In this paper we study very large‐scale neighborhoods for the minimum total...
Reoptimization of the Shortest Common Superstring Problem
Reoptimization of the Shortest Common Superstring Problem
2011,
A reoptimization problem describes the following scenario: given an instance of an...
A caving degree based flake arrangement approach for the container loading problem
A caving degree based flake arrangement approach for the container loading problem
2010,
A caving degree based flake arrangement (CDFA) approach for the NP‐hard...
Analisis Experimental Del Costo Computacional Del Problema 2+p-Sat Aleatorio
Analisis Experimental Del Costo Computacional Del Problema 2+p-Sat Aleatorio
2004,
Random 2+p-SAT problem interpolates between the polynomial-time random 2-SAT...
An Online Algorithm for a Problem in Scheduling with Set‐ups and Release Times
An Online Algorithm for a Problem in Scheduling with Set‐ups and Release Times
2011,
We address the problem of sequential single machine scheduling of jobs with release...
Crossing Number and Weighted Crossing Number of Near‐Planar Graphs
Crossing Number and Weighted Crossing Number of Near‐Planar Graphs
2011,
A nonplanar graph G is near‐planar if it contains an edge e such that G - e is...
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k‐Way Cut Problem
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k‐Way Cut Problem
2011,
For an edge‐weighted connected undirected graph, the minimum k ‐way cut...
Haplotype inference with pseudo‐Boolean optimization
Haplotype inference with pseudo‐Boolean optimization
2011,
The fast development of sequencing techniques in the recent past has required an...
The multi‐terminal maximum‐flow network‐interdiction problem
The multi‐terminal maximum‐flow network‐interdiction problem
2011,
This paper defines and studies the multi‐terminal maximum‐flow...
The case for strategic oscillation
The case for strategic oscillation
2011,
We study a ‘hard’ optimization problem for metaheuristic search, where a...
Scheduling UET‐tasks on a star network: complexity and approximation
Scheduling UET‐tasks on a star network: complexity and approximation
2011,
In this article we investigate complexity and approximation on a processor network...
Improved Algorithms for Maximum Agreement and Compatible Supertrees
Improved Algorithms for Maximum Agreement and Compatible Supertrees
2011,
Consider a set of labels L and a set of unordered trees 𝒯={𝒯 (1)...
NP-hard problems and test problems for global concave minimization methods
NP-hard problems and test problems for global concave minimization methods
1991,
This paper presents a new method of obtaining hard test problems for global concave...
Openshop scheduling with machine dependent processing times
Openshop scheduling with machine dependent processing times
1992,
This paper examines the openshop problem with machine dependent processing times. Two...
A polynomial-time algorithm for computing the yolk in fixed dimension
A polynomial-time algorithm for computing the yolk in fixed dimension
1992,
The yolk, developed by Ferejohn, McKelvey and Packel and McKelvey, is a key solution...
Deciding uniqueness in norm maximization
Deciding uniqueness in norm maximization
1992,
NP-hardness is established for the problem whose instance is a system of linear...
Papers per page: