On the computational complexity of bridgecard

Bridgecard is a classical trick-taking game utilizing a standard 52-card deck, in which four players in two competing partnerships attempt to “win” each round, i.e. trick. Existing theories and analysis have already attempted to show correlations between system designs and other technical issues with parts of the game, specifically the “Bidding” phase, but this paper will be the first to attempt to initiate a theoretical study on this game by formulating it into an optimization problem. This paper will provide both an analysis of the computational complexity of the problem, and propose exact, as well as, approximation algorithms.     

Algorithms and time complexity of the request-service problem

Given a number of users each of which provides a set of services with a cost for each service and has a set of requests to be satisfied, the goal of the request-service problem is to find a feasible solution that satisfies all requests of each user with minimum cost. In addition, a feasible solution must satisfy an additional constraint. Specifically, if user A provides a service to user B, B should provide a service back to A either directly or indirectly through other users. In this paper, we studied the complexity of this problem. We show that there exists a polynomial time algorithm that can compute a feasible solution with minimum cost if such a solution exists. However, if a feasible solution does not exist, the problem of maximizing the number of satisfied users (i.e., all requests of the users are satisfied) is NP-hard.     

The computational complexity of QoS measures for orchestrations

We consider Web services defined by orchestrations in the Orc language and two natural quality of services measures, the number of outputs and a discrete version of the first response time. We analyse first those subfamilies of finite orchestrations in which the measures are well defined and consider their evaluation in both reliable and probabilistic unreliable environments. On those subfamilies in which the QoS measures are well defined, we consider a set of natural related problems and analyse its computational complexity. In general our results show a clear picture of the difficulty of computing the proposed QoS measures with respect to the expressiveness of the subfamilies of Orc. Only in few cases the problems are solvable in polynomial time pointing out the computational difficulty of evaluating QoS measures even in simplified models.     

New analysis and computational study for the planar connected dominating set problem

The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. (Algorithmica 58:790–810 2010) introduce a branch-decomposition based algorithm design technique for NP-hard problems in planar graphs and give an algorithm (DPBF algorithm) which solves the planar CDS problem in \(O(2^{9.822\sqrt{n}}n+n^3)\) time and \(O(2^{8.11\sqrt{n}}n+n^3)\) time, with a conventional method and fast matrix multiplication in the dynamic programming step of the algorithm, respectively. We show that DPBF algorithm solves the planar CDS problem in \(O(2^{9.8\sqrt{n}}n+n^3)\) time with a conventional method and in \(O(2^{8.08\sqrt{n}}n+n^3)\) time with a fast matrix multiplication. For a graph \(G\), let \({\hbox {bw}}(G)\) be the branchwidth of \(G\) and \(\gamma _c(G)\) be the connected dominating number of \(G\). We prove \({\hbox {bw}}(G)\le 2\sqrt{10\gamma _c(G)}+32\). From this result, the planar CDS problem admits an \(O(2^{23.54\sqrt{\gamma _c(G)}}\gamma _c(G)+n^3)\) time fixed-parameter algorithm. We report computational study results on the practical performance of DPBF algorithm, which show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical analysis. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space.     

The complexity of influence maximization problem in the deterministic linear threshold model

The influence maximization is an important problem in the field of social network. Informally it is to select few people to be activated in a social network such that their aggregated influence can make as many as possible people active. Kempe et al. gave a $(1-{1 \over e})$ -approximation algorithm for this problem in the linear threshold model and the independent cascade model. In addition, Chen et al. proved that the exact computation of the influence given a seed set is #P-hard in the linear threshold model. Both of the two models are based on randomized propagation, however such information might be obtained by surveys and data mining techniques. This will make great difference on the complexity of the problem. In this note, we study the complexity of the influence maximization problem in deterministic linear threshold model. We show that in the deterministic linear threshold model, there is no n ^1??? -factor polynomial time approximation for the problem unless P=NP. We also show that the exact computation of the influence given a seed set can be solved in polynomial time.     

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.     

Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity

Journal of Combinatorial Optimization - Given $$\lambda >0$$ , an undirected complete graph $$G=(V,E)$$ with nonnegative edge-weight function obeying the triangle inequality and a depot...     

Critical edges/nodes for the minimum spanning tree problem: complexity and approximation

In this paper, we study the complexity and the approximation of the k most vital edges (nodes) and min edge (node) blocker versions for the minimum spanning tree problem (MST). We show that the k most vital edges MST problem is NP-hard even for complete graphs with weights 0 or 1 and 3-approximable for graphs with weights 0 or 1. We also prove that the k most vital nodes MST problem is not approximable within a factor n ^1?? , for any ?>0, unless NP=ZPP, even for complete graphs of order n with weights 0 or 1. Furthermore, we show that the min edge blocker MST problem is NP-hard even for complete graphs with weights 0 or 1 and that the min node blocker MST problem is NP-hard to approximate within a factor 1.36 even for graphs with weights 0 or 1.     

Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.     

A note on the complexity of the problem of two-agent scheduling on a single machine

We consider a two-agent scheduling problem on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the number of tardy jobs of the second agent cannot exceed a given number. It is reported in the literature that the complexity of this problem is still open. We show in this paper that this problem is NP-hard under high multiplicity encoding and can be solved in pseudo-polynomial time under binary encoding. When the first agent's objective is to minimize the total weighted completion time, we show that the problem is strongly NP-hard even when the number of tardy jobs of the second agent is restricted to be zero.     

Scheduling internal audit activities: a stochastic combinatorial optimization problem

The problem of finding the optimal timing of audit activities within an organisation has been addressed by many researchers. We propose a stochastic programming formulation with Mixed Integer Linear Programming (MILP) and Constraint Programming (CP) certainty-equivalent models. In experiments neither approach dominates the other. However, the CP approach is orders of magnitude faster for large audit times, and almost as fast as the MILP approach for small audit times. This work generalises a previous approach by relaxing the assumption of instantaneous audits, and by prohibiting concurrent auditing.     

The shift minimisation personnel task scheduling problem: A new hybrid approach and computational insights

Assigning scheduled tasks to a multi-skilled workforce is a known NP-complete problem with many applications in health care, services, logistics and manufacturing. Optimising the use and composition of costly and scarce resources such as staff has major implications on any organisation׳s health. The present paper introduces a new, versatile two-phase matheuristic approach to the shift minimisation personnel task scheduling problem, which considers assigning tasks to a set of multi-skilled employees, whose working times have been determined beforehand. Computational results show that the new hybrid method is capable of finding, for the first time, optimal solutions for all benchmark instances from the literature, in very limited computation time. The influence of a set of problem instance features on the performance of different algorithms is investigated in order to discover what makes particular problem instances harder than others. These insights are useful when deciding on organisational policies to better manage various operational aspects related to workforce. The empirical hardness results enable to generate hard problem instances. A set of new challenging instances is now available to the academic community.     

On the parameterized complexity of the Multi-MCT and Multi-MCST problems

The comparison of tree structured data is widespread since trees can be used to represent wide varieties of data, such as XML data, evolutionary histories, or carbohydrate structures. Two graph-theoretical problems used in the comparison of such data are the problems of finding the maximum common subtree (MCT) and the minimum common supertree (MCST) of two trees. These problems generalize to the problem of finding the MCT and MCST of multiple trees (Multi-MCT and Multi-MCST, respectively). In this paper, we prove parameterized complexity hardness results for the different parameterized versions of the Multi-MCT and Multi-MCST problem under isomorphic embeddings.     

智能体建模和资本市场复杂性

以复杂适应系统的思想和智能体建模的方法研究资本市场复杂性是新兴的有价值的研究领域,阐述了资本市场作为复杂适应系统的动力机制,介绍了这一领域一个重要模型———少数派博弈(minority game,MG)模型.仿真发现,处于拥挤阶段的MG具有和实际市场相近的收益率分布.进一步扩展标准MG,提出了快速适应的少数派博弈模型,仿真结果显示,新的模型有着和真实市场相同的特征:收益率分布的尖峰和肥尾现象,揭示了资本市场复杂性的内部动力学机理.     

Integrated Order Scheduling and Packing

We consider an integrated production–distribution scheduling model in a make‐to‐order supply chain consisting of one supplier and one customer. The supplier receives a set of orders from the customer at the beginning of a planning horizon. The supplier needs to process all the orders at a single production line, pack the completed orders to form delivery batches, and deliver the batches to the customer. Each order has a weight, and the total weight of the orders packed in a batch must not exceed the capacity of the delivery batch. Each delivery batch incurs a fixed distribution cost. The problem is to find jointly a schedule for order processing and a way of packing completed orders to form delivery batches such that the total distribution cost (or equivalently, the number of delivery batches) is minimized subject to the constraint that a given customer service level is guaranteed. We consider two customer service constraints—meeting the given deadlines of the orders; or requiring the average delivery lead time of the orders to be within a given threshold. Several problems of the model with each of those constraints are considered. We clarify the complexity of each problem and develop fast heuristics for the NP‐hard problems and analyze their worst‐case performance bounds. Our computational results indicate that all the heuristics are capable of generating near optimal solutions quickly for the respective problems.     

Parameterized complexity of k-anonymity: hardness and tractability

The problem of publishing personal data without giving up privacy is becoming increasingly important. A precise formalization that has been recently proposed is the k-anonymity, where the rows of a table are partitioned into clusters of sizes at least k and all rows in a cluster become the same tuple after the suppression of some entries. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is hard even when the stored values are over a binary alphabet or the table consists of a bounded number of columns. In this paper we study how the complexity of the problem is influenced by different parameters. First we show that the problem is W[1]-hard when parameterized by the value of the solution (and k). Then we exhibit a fixed-parameter algorithm when the problem is parameterized by the number of columns and the number of different values in any column. Finally, we prove that k-anonymity is still APX-hard even when restricting to instances with 3 columns and k=3.