A complexity dichotomy and a new boundary class for the dominating set problem

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.     

Maximum latency scheduling problem on two-person cooperative games

This paper studies a two-person cooperative game in which a set of jobs has to be processed jointly by two people. Each of them has a single machine and his processing cost is defined as the minimum value of the maximum latency of his negotiably assigned jobs. The objective is to maximize the multiplication of their rational positive cooperative profits. In the case where all jobs have the same processing time, if they have a common due date, the problem is polynomial-time solvable; if due dates can be different, there exits an optimal schedule in which the jobs assigned to each person are scheduled in Earlier Due Date first (EDD) order and a polynomial-time dynamic programming is further proposed. In the case where processing times can be different, the NP-completeness of this problem is proved, and a pseudo-polynomial-time dynamic programming algorithm is developed.     

An Approximation for Minimum Multicast Route in Optical Networks with Nonsplitting Nodes

Consider the problem of computing the minimum-weight multicast route in an optical network with both nonsplitting and splitting nodes. This problem can be reduced to the minimum Hamiltonian path problem when all nodes are nonsplitting, and the Steiner minimum tree problem when all nodes are splitting. Therefore, the problem is NP-hard. Previously, the best known polynomial-time approximation has the performance ratio 3. In this paper, we present a new polynomial-time approximation with performance ratio of 1+ρ, where ρ is the best known approximation performance ratio for the Steiner minimum tree in graph and it has been known that ρ < 1.55. Support in part by National Science Foundation under grants CCF-0514796 and CNS-0524429     

A novel approach for detecting multiple rumor sources in networks with partial observations

Locating source of information diffusion in networks has very important applications such as locating the sources of epidemics, news/rumors in social networks or online computer virus. In this paper, we consider detecting multiple rumor sources from a deterministic point of view by modeling it as the set resolving set (SRS) problem. Let G be a network on n nodes. A node subset K is an SRS of G if all detectable node sets are distinguishable by K. The problem of multiple rumor source detection (MRSD) in the network can be modeled as finding an SRS K with the smallest cardinality. In this paper, we propose a polynomial-time greedy algorithm for finding a minimum SRS in a general network, achieving performance ratio \(O(\ln n)\). This is the first work establishing a relation between the MRSD problem and a deterministic concept of SRS, and a first work to give the minimum SRS problem a polynomial-time performance-guaranteed approximation algorithm. Our framework suggests a robust and efficient approach for estimating multiple rumor sources independent of diffusion models in networks.     

The popular matching and condensation problems under matroid constraints

The popular matching problem introduced by Abraham, Irving, Kavitha, and Mehlhorn is a matching problem in which there exist applicants and posts, and applicants have preference lists over posts. A matching M is said to be popular, if there exists no other matching N such that the number of applicants that prefer N to M is larger than the number of applicants that prefer M to N. The goal of this problem is to decide whether there exists a popular matching, and find a popular matching if one exists. In this paper, we first consider a matroid generalization of the popular matching problem with strict preference lists, and give a polynomial-time algorithm for this problem. In the second half of this paper, we consider the problem of transforming a given instance of a matroid generalization of the popular matching problem with strict preference lists by deleting a minimum number of applicants so that it has a popular matching. This problem is a matroid generalization of the popular condensation problem with strict preference lists introduced by Wu, Lin, Wang, and Chao. By using the results in the first half, we give a polynomial-time algorithm for this problem.     

需求替代的两产品动态批量最优预测时阈研究

研究了存在需求单向替代的两产品动态批量决策的最优预测时阈问题.构建了包含替代成本、生产转换成本和库存成本在内的成本最小化模型,分析得出在只存在3类再生点(Ⅰ类、Ⅱ类和Ⅲ类)情形下的再生点单调性特征.同时,设计出了多项式时间的前向动态规划算法.运用数值试验分析了最优预测时阈与生产转换成本、替代成本、需求特征(需求增长性和...     

Staying safe and visible via message sharing in online social networks

As an imperative channel for fast information propagation, online social networks (OSNs) also have their defects. One of them is the information leakage, i.e., information could be spread via OSNs to the users whom we are not willing to share with. Thus the problem of constructing a circle of trust to share information with as many friends as possible without further spreading it to unwanted targets has become a challenging research topic but still remained open. Our work is the first attempt to study the Maximum Circle of Trust problem seeking to share the information with the maximum expected number of poster’s friends such that the information spread to the unwanted targets is brought to its knees. First, we consider a special and more practical case with the two-hop information propagation and a single unwanted target. In this case, we show that this problem is NP-hard, which denies the existence of an exact polynomial-time algorithm. We thus propose a Fully Polynomial-Time Approximation Scheme (FPTAS), which can not only adjust any allowable performance error bound but also run in polynomial time with both the input size and allowed error. FPTAS is the best approximation solution one can ever wish for an NP-hard problem. We next consider the number of unwanted targets is bounded and prove that there does not exist an FPTAS in this case. Instead, we design a Polynomial-Time Approximation Scheme (PTAS) in which the allowable error can also be controlled. When the number of unwanted targets are not bounded, we provide a randomized algorithm, along with the analytical theoretical bound and inapproximaibility result. Finally, we consider a general case with many hops information propagation and further show its #P-hardness and propose an effective Iterative Circle of Trust Detection (ICTD) algorithm based on a novel greedy function. An extensive experiment on various real-world OSNs has validated the effectiveness of our proposed approximation and ICTD algorithms. Such an extensive experiment also highlights several important observations on information leakage which help to sharpen the security of OSNs in the future.     

The weighted link ring loading problem

In the weighted link ring loading problem, we are given an n-node undirected ring network. Each of its links is associated with a weight. Traffic demands are given for each pair of nodes in the ring. The load of a link is the sum of the flows routed through the link, and the weighted load of a link is the product of its weight and the smallest integer not less than its load. The objective of the problem is to find a routing scheme such that the maximum weighted load on the ring is minimized. In this paper we consider three variants: (i) demands may be split into two parts, and then each part is sent in a different direction; (ii) demands are allowed to be split into two parts but restricted to be integrally split; (iii) each demand must be entirely routed in either of the two directions, clockwise or counterclockwise. We first prove that the first variant is polynomially solvable. We then present a pseudo-polynomial time algorithm for the second one. Finally, for the third one, whose NP-hardness can be drawn from the result in the literature, we derive a polynomial-time approximation scheme (PTAS).     

Improving robustness of next-hop routing

A weakness of next-hop routing is that following a link or router failure there may be no routes between some source-destination pairs, or packets may get stuck in a routing loop as the protocol operates to establish new routes. In this article, we address these weaknesses by describing mechanisms to choose alternate next hops. Our first contribution is to model the scenario as the following tree augmentation problem. Consider a mixed graph where some edges are directed and some undirected. The directed edges form a spanning tree pointing towards the common destination node. Each directed edge represents the unique next hop in the routing protocol. Our goal is to direct the undirected edges so that the resulting graph remains acyclic and the number of nodes with outdegree two or more is maximized. These nodes represent those with alternative next hops in their routing paths. We show that tree augmentation is NP-hard in general and present a simple \(\frac{1}{2}\)-approximation algorithm. We also study 3 special cases. We give exact polynomial-time algorithms for when the input spanning tree consists of exactly 2 directed paths or when the input graph has bounded treewidth. For planar graphs, we present a polynomial-time approximation scheme when the input tree is a breadth-first search tree. To the best of our knowledge, tree augmentation has not been previously studied.     

Fair task allocation in transportation

Task allocation problems have traditionally focused on cost optimization. However, more and more attention is being given to cases in which cost should not always be the sole or major consideration. In this paper we study a fair task allocation problem in transportation where an optimal allocation not only has low cost but more importantly, it distributes tasks as even as possible among heterogeneous participants who have different capacities and costs to execute tasks. To tackle this fair minimum cost allocation problem we analyze and solve it in two parts using two novel polynomial-time algorithms. We show that despite the new fairness criterion, the proposed algorithms can solve the fair minimum cost allocation problem optimally in polynomial-time. In addition, we conduct an extensive set of experiments to investigate the trade-off between cost minimization and fairness. Our experimental results demonstrate the benefit of factoring fairness into task allocation. Among the majority of test instances, fairness comes with a very small price in terms of cost.     

Batch-Processing Scheduling with Setup Times

The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.     

On single machine scheduling with resource constraint

The single machine scheduling with resource constraint is a nonlinear combinatorial optimization problem in cloud computing applications. Given a set of jobs and certain resource, the problem is to find a permutation of jobs and a distribution of resource to optimize certain objective function. The processing time of each job is a nonlinear function with respect to the resource assigned to it. In this paper, we propose a naive algorithm and study a subproblem in the algorithm that suppose the permutation of jobs is also given, how to find a resource distribution to minimize the total weighted flow time. We found a polynomial-time optimal solution for a special case and an approximation solution in general case.     

A “maximum node clustering” problem

In this note we introduce a graph problem, called Maximum Node Clustering (MNC). We prove that the problem (which is easily shown to be strongly NP-complete) can be approximated in polynomial time within a ratio arbitrarily close to 2. For the special case where the graph is a tree, the problem is NP-complete in the ordinary sense; for this case we present a pseudopolynomial algorithm based on dynamic programming, and a related Fully Polynomial Time Approximation Scheme (FPTAS). Also, the tree case is shown to be exactly solvable in time, where n is the number of nodes.     

Constrained pairwise and center-star sequences alignment problems

This paper considers the minimax regret vertex 2-sink location problem in a dynamic path network with positive edge lengths and uniform edge capacity. Let \(P\) be an undirected path graph of \(n\) vertices, and the weight (initial supply) of every vertex is known as an interval. The problem is to find two vertices \(x\) and \(y\) as two sinks on the path such that all the weights can evacuate to \(x\) and \(y\) with minimum regret of evacuation time in case of an emergency for any possible weight distribution. We present an \(O(n^3\log n)\) time algorithm.     

Anonymizing binary and small tables is hard to approximate

The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization recently proposed is the k-anonymity. This approach requires that the rows in a table are clustered in sets of size at least k and that all the rows in a cluster become the same tuple, after the suppression of some records. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be NP-hard when the values are over a ternary alphabet, k=3 and the rows length is unbounded. In this paper we give a lower bound on the approximation factor that any polynomial-time algorithm can achieve on two restrictions of the problem, namely (i) when the records values are over a binary alphabet and k=3, and (ii) when the records have length at most 8 and k=4, showing that these restrictions of the problem are APX-hard.     

Models for the single-vehicle preemptive pickup and delivery problem

In this paper, we study a variant of the well-known single-vehicle pickup and delivery problem where the demands can be unloaded/reloaded at any node. By proving new complexity results, we give the minimum information which is necessary to represent feasible solutions. Using this, we present integer linear programs for both the unitary and the general versions. We then show that the associated linear relaxations are polynomial-time solvable and present some computational results.     

Solving the flight gate assignment problem using dynamic programming

This paper considers the problem of assigning flights to airport gates—a problem which is NP-hard in general. We focus on a special case in which the maximization of flight/gate preference scores is the only objective. We show that for a variable number of flights and gates, this problem is still NP-hard. For a fixed number of gates, we present a dynamic programming approach that solves the flight assignment problem in linear time with respect to the number of flights. Computational results using real life data from a major European airport prove the practical relevance of this approach.     

On the Complexity of Constructing Evolutionary Trees

In this paper we study a few important tree optimization problems with applications to computational biology. These problems ask for trees that are consistent with an as large part of the given data as possible. We show that the maximum homeomorphic agreement subtree problem cannot be approximated within a factor of , where N is the input size, for any 0 in polynomial time unless P = NP, even if all the given trees are of height 2. On the other hand, we present an O(N log N)-time heuristic for the restriction of this problem to instances with O(1) trees of height O(1) yielding solutions within a constant factor of the optimum. We prove that the maximum inferred consensus tree problem is NP-complete, and provide a simple, fast heuristic for it yielding solutions within one third of the optimum. We also present a more specialized polynomial-time heuristic for the maximum inferred local consensus tree problem.     

Modelling and analysis of dynamic capacity complexity in multi-stage production

The uncertainty associated with managing dynamic capacity problem is the main source of its complexity. This article presents a system dynamics approach to model and analyse operational complexity of dynamic capacity in multi-stage production. The unique feature of this approach is that it captures the stochastic nature of three main sources of complexity associated with dynamic capacity. These are the demand, internal manufacturing delay and capacity scalability delay. The developed model was demonstrated by an industrial case study of multi-stage printed circuit board assembly line. The analysis of simulation experiments showed that ignoring complexity sources can lead to wrong decisions concerning both scaling levels and backlog management decisions. In addition, a general trade-off between the controllability and complexity of the dynamic capacity was illustrated. Finally, comparative analysis of the effect of each of these sources on the complexity level revealed that internal delay has the highest impact on dynamic capacity efficiency. Guidelines and recommendations for better capacity management and reduction of its complexity are presented.     

局内动态配送车调度管理及其竞争策略

提出了动态物流配送车辆调度优化问题——配送车在一度量空间中进行服务,度量空间中的任何一节点可能在任何时间提出服务请求,要求配送车将该点处的货物运送到另一点,每一个服务请求都有一个服务期限,若在规定的时间内某一服务请求不能被满足则将被取消,在考虑装/卸货所用时间的情况下,决策者如何以局内方式确定调度策略,使配送车完成的服务请求数最多.针对该不确定性条件下的管理决策问题,给出了两种局内管理策略,并利用局内问题及竞争分析理论,给出了不同载重量下(Q=1和Q=∞)的两种策略的竞争比.