团队成员选择的模型及算法

本针对组织中组建团队或重组现有团队时的成员选择问题，提出了反映团队成员之间、成员和团队之间关系的群体效用模型，并根据此模型进行团队成员的选择，从而把团队成员选择问题转化为一个组合优化问题。证明了基于群体效用模型进行团队成员选择的问题是NP-hard问题，并且提出了基于ORASP技术和禁忌算法的启发式算法，最后给出了算例。     

Solving some NP-complete problems using split decomposition

We show how to use the split decomposition to solve some NP-hard optimization problems on graphs. We give algorithms for clique problem and domination-type problems. Our main result is an algorithm to compute a coloration of a graph using its split decomposition. Finally we show that the clique-width of a graph is bounded if and only if the clique-width of each representative graph in its split decomposition is bounded.     

On the minimum corridor connection problem and other generalized geometric problems

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into “rooms”, one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.     

Tree-edges deletion problems with bounded diameter obstruction sets

We study the following problem: given a tree G and a finite set of trees H, find a subset O of the edges of G such that G-O does not contain a subtree isomorphic to a tree from H, and O has minimum cardinality. We give sharp boundaries on the tractability of this problem: the problem is polynomial when all the trees in H have diameter at most 5, while it is NP-hard when all the trees in H have diameter at most 6. We also show that the problem is polynomial when every tree in H has at most one vertex with degree more than 2, while it is NP-hard when the trees in H can have two such vertices.The polynomial-time algorithms use a variation of a known technique for solving graph problems. While the standard technique is based on defining an equivalence relation on graphs, we define a quasiorder. This new variation might be useful for giving more efficient algorithm for other graph problems.     

On the Hardness of Approximating the Chromatic Number

k -colorable for some fixed . Our main result is that it is NP-hard to find a 4-coloring of a 3-chromatic graph. As an immediate corollary we obtain that it is NP-hard to color a k-chromatic graph with at most colors. We also give simple proofs of two results of Lund and Yannakakis [20]. The first result shows that it is NP-hard to approximate the chromatic number to within for some fixed ε > 0. We point here that this hardness result applies only to graphs with large chromatic numbers. The second result shows that for any positive constant h, there exists an integer , such that it is NP-hard to decide whether a given graph G is -chromatic or any coloring of G requires colors. Received April 11, 1997/Revised June 10, 1999     

A polynomial case of the parsimony haplotyping problem

The parsimony haplotyping problem was shown to be NP-hard when each genotype had k?3ambiguous positions, while the case for k?2 was open. In this paper, we show that the case for k?2 is polynomial, and we give approximation and FPT algorithms for the general case of k?0 ambiguous positions.     

Routing multi-class traffic flows in the plane

We study a class of multi-commodity flow problems in geometric domains: For a given planar domain P populated with obstacles (holes) of K?2types, compute a set of thick paths from a “source” edge of P to a “sink” edge of P for vehicles of K distinct classes. Each class k of vehicle has a given set, Ok, of obstacles it must avoid and a certain width, wk, of path it requires. The problem is to determine if it is possible to route Nk width-wk paths for class k vehicles from source to sink, with each path avoiding the requisite set Ok of obstacles, and no two paths overlapping. This form of multi-commodity flow in two-dimensional domains arises in computing throughput capacity for multiple classes of aircraft in an airspace impacted by different types of constraints, such as those arising from weather hazards.We give both algorithmic theory results and experimental results.We show hardness of many versions of the problem by proving that two simple variants are NP-hard even in the case K=2. If w₁=w₂=1, then the problem is NP-hard even when O₁=∅. If w₁=2, w₂=3, then the problem is NP-hard even when O₁=O₂. In contrast, the problem for a single width and a single type of obstacles is polynomially solvable.We present approximation algorithms for the multi-criteria optimization problems that arise when trying to maximize the number of routable paths. We also give a polynomial-time algorithm for the case in which the number of holes in the input domain is bounded.Finally, we give experimental results based on an implementation of our methods and experiment with enhanced heuristics for efficient solutions in practice. Our algorithms are being utilized in simulations with NASA?s Future Air traffic management Concepts Evaluation Tool (FACET). We report on experimental results based on applying our algorithms to weather-impacted airspaces, comparing heuristic strategies for searching for feasible path orderings and for computing short multi-class routes. Our results show that multi-class routes can feasibly be computed on real weather data instances on the scale required in air traffic management applications.     

On the complexity of scheduling unit-time jobs with OR-precedence constraints

We present various complexity results for scheduling unit-time jobs subject to OR-precedence constraints. We prove that minimizing the total weighted completion time is strongly NP-hard, even on a single machine. In contrast, we give a polynomial-time algorithm for minimizing the makespan and the total completion time on identical parallel machines.     

Parallel machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

Approximating the balanced minimum evolution problem

We prove a strong inapproximability result for the Balanced Minimum Evolution Problem. Our proof also implies that the problem remains NP-hard even when restricted to metric instances. Furthermore, we give a MST-based 2-approximation algorithm for the problem for such instances.     

Strong NP-hardness of AC power flows feasibility

We prove that testing feasibility for an AC power flow system is a strongly NP-hard problem.     

Scheduling problems in master-slave model

We consider scheduling problems in the master slave model, which was introduced by Sahni in 1996. The goal is to minimize the makespan and the total completion time. It has been shown that the problem of minimizing makespan is NP-hard. Sahni and Vairaktarakis developed some approximation algorithms to generate schedules whose makespan is at most constant times the optimal. In this paper, we show that the problem of minimizing total completion time is NP-hard in the strong sense. Then we develop algorithms to generate schedules whose total completion time and makespan are both bounded by some constants times their optimal values. Research supported in part by the National Science Foundation through grant DMI-0300156.     

Solving the 0–1 proportional knapsack problem by sampling

In this paper, we deal with the proportional knapsack problem that is a variation on the ordinary knapsack problem. In the proportional knapsack problem, we look at filling an urn with objects having two characteristics: color and weight. The colors of the objects in the urn should be proportional to the distribution of the colors in the object universe, and the total weight of the objects in the urn should be as close as possible to the capacity of the urn. The formulation of the problem was motivated by a real-life application from the area of finance, called a dollar roll. We show that the proportional knapsack problem is NP-hard, and then, using sampling, develop a heuristic procedure for solving the problem.Partial support from the Fund for the Promotion of Research and from the Alexander Goldberg Memorial Fund at Technion is gratefully acknowledged.     

On guarding the vertices of rectilinear domains

We prove that guarding the vertices of a rectilinear polygon P, whether by guards lying at vertices of P, or by guards lying on the boundary of P, or by guards lying anywhere in P, is NP-hard. For the first two proofs (i.e., vertex guards and boundary guards), we construct a reduction from minimum piercing of 2-intervals. The third proof is somewhat simpler; it is obtained by adapting a known reduction from minimum line cover.

We also consider the problem of guarding the vertices of a 1.5D rectilinear terrain. We establish an interesting connection between this problem and the problem of computing a minimum clique cover in chordal graphs. This connection yields a 2-approximation algorithm for the guarding problem.     

Aspects of a multivariate complexity analysis for Rectangle Tiling

We initiate a parameterized complexity study of the NP-hard problem to tile a positive integer matrix with rectangles, keeping the number of tiles and their maximum weight small. We show that the problem remains NP-hard even for binary matrices only using 1×1 and 2×2-squares as tiles and provide insight into the influence of naturally occurring parameters on the problem’s complexity.     

A hybrid genetic algorithm for the repetition free longest common subsequence problem

Computing the longest common subsequence of two sequences is one of the most studied algorithmic problems. In this work we focus on a particular variant of the problem, called repetition free longest common subsequence (RF-LCS$\text{<small-caps>RF-LCS</small-caps>}$), which has been proved to be NP-hard. We propose a hybrid genetic algorithm, which combines standard genetic algorithms and estimation of distribution algorithms, to solve this problem. An experimental comparison with some well-known approximation algorithms shows the suitability of the proposed technique.     

Scheduling unit-length jobs with precedence constraints of small height

We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.     

Heuristic algorithms for the 2-period balanced Travelling Salesman Problem in Euclidean graphs

In the 2-period Travelling Salesman Problem some nodes, called double nodes, are visited in both of two periods while the remaining ones, called single nodes, are visited in either one of the periods. In this paper we study the case in which a balance constraint is also introduced. We require that the difference between the number of visited nodes in the two periods must be below a fixed threshold. Moreover, we suppose that distances between nodes are Euclidean. The problem is NP-hard, and exact methods, now available, appear inadequate. Here, we propose three heuristics. Computational experiences and a comparison between the algorithms are also given.     

Minimizing average completion time in the presence of release dates

A natural and basic problem in scheduling theory is to provide good average quality of service to a stream of jobs that arrive over time. In this paper we consider the problem of schedulingn jobs that are released over time in order to minimize the average completion time of the set of jobs. In contrast to the problem of minimizing average completion time when all jobs are available at time 0, all the problems that we consider are NP-hard, and essentially nothing was known about constructing good approximations in polynomial time. We give the first constant-factor approximation algorithms for several variants of the single and parallel machine models. Many of the algorithms are based on interesting algorithmic and structural relationships between preemptive and nonpreemptive schedules and linear programming relaxations of both. Many of the algorithms generalize to the minimization of averageweighted completion time as well. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This work was performed under US Department of Energy contract number DE-AC04-76AL85000.Research partly supported by NSF Award CCR-9308701, a Walter Burke Research Initiation Award and a Dartmouth College Research Initiation Award.Research partially supported by NSF Research Initiation Award CCR-9211494 and a grant from the New York State Science and Technology Foundation, through its Center for Advanced Technology in Telecommunications.     

A polynomially solvable case of the pooling problem

Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomial time by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border between (strongly) NP-hard and polynomially solvable cases of the pooling problem.