On the cores of games arising from integer edge covering functions of graphs

In this paper, we study cooperative games arising from integer edge covering problems on graphs. We introduce two games, a rigid k-edge covering game and its relaxed game, as generalizations of a rigid edge covering game and its relaxed game studied by Liu and Fang (2007). Then we give a characterization of the cores of both games, find relationships between them, and give necessary and sufficient conditions for the balancedness of a rigid k-edge covering game and its relaxed game.     

A better constant-factor approximation for weighted dominating set in unit disk graph

This paper presents a (10+ε)-approximation algorithm to compute minimum-weight connected dominating set (MWCDS) in unit disk graph. MWCDS is to select a vertex subset with minimum weight for a given unit disk graph, such that each vertex of the graph is contained in this subset or has a neighbor in this subset. Besides, the subgraph induced by this vertex subset is connected. Our algorithm is composed of two phases: the first phase computes a dominating set, which has approximation ratio 6+ε (ε is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4. This work is supported in part by National Science Foundation under grant CCF-9208913 and CCF-0728851; and also supported by NSFC (60603003) and XJEDU.     

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.     

碳交易机制下零售商合作的费用分配研究

在一个由单供应商和多个零售商组成的二阶供应链中，研究碳交易机制下多零售商合作的订货决策问题。对完全信息下零售商合作的费用分配问题，应用合作博弈理论建立了费用分配的博弈模型，证明了博弈为子模博弈且设计了属于核心的费用分配方案，该方案不仅可通过总体单调分配机制实现而且可使大联盟长远稳定。对不完全信息下零售商合作的费用分配问题，证明了纯策略纳什均衡的存在性。研究结果表明，零售商的合作不仅能降低总费用，而且能降低碳排放量；各零售商在不完全信息下分担的费用大于完全信息下分担的费用。     

Algorithms for the minimum weight k-fold (connected) dominating set problem

In this paper, we study the problem of computing a minimum weight k-fold dominating set (MWkDS) or a minimum weight k-fold connected dominating set (MWkCDS) in a unit ball graph (UBG). Using slab decomposition and dynamic programming, we give two exact algorithms for the computation of MWkDS and MWkCDS which can be executed in polynomial time if the thickness of the graph is bounded above.     

A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs

In the minimum weighted dominating set problem (MWDS), we are given a unit disk graph with non-negative weight on each vertex. The MWDS seeks a subset of the vertices of the graph with minimum total weight such that each vertex of the graph is either in the subset or adjacent to some nodes in the subset. A?weight function is called smooth, if the ratio of the weights of any two adjacent nodes is upper bounded by a constant. MWDS is known to be NP-hard. In this paper, we give the first polynomial time approximation scheme (PTAS) for MWDS with smooth weights on unit disk graphs, which achieves a (1+ε)-approximation for MWDS, for any ε>0.     

Strengthened 0-1 linear formulation for the daily satellite mission planning

In this paper, we compare several 0-1 linear programs for solving the satellite mission planning problem. We prove that one of them presents a smaller integrality gap. Our explanation is based on stable set polytope formulations for perfect graphs.     

面向成套订单问题的工艺规划与排序的集成研究

本文从工艺规划与排序的集成优化角度研究了成套订单问题^[1],克服了单独研究工艺规划和排序局部优化的局限性.文章中考虑了同一工件内部各道工序之间存在的优先加工限制,以及工件在不同机器上加工需要转移时间和工序间接连加工需要机器调整时间的情况,建立了成套订单问题的集成排序模型,并提出了针对求解大规模问题的基于遗传算法的启发式算法,最后通过一个算例对所研究的集成排序问题和所提出的算法进行了说明,计算结果表明了算法的有效性.     

Coalition Formation and Cost Allocation for Joint Replenishment Systems

This paper focuses on the issues of coalition formation and cost allocation in a joint replenishment system involving a set of independent and freely interacting retailers purchasing an item from one supplier to meet a deterministic demand. The papers dealing with this problem are mainly focused on supperadditive games, where the cost savings associated with a coalition increase with the number of players in the coalition. The most relevant question addressed then is how to allocate the savings to the players. In this paper, we propose to go further by dealing with a non‐supperadditive game, where a set of independent retailers have the common understanding to share the cost savings according to the cost‐based proportional rule. In this setting, the global cost optimization is no longer a relevant approach to identify appealing coalitions for any retailer. Here, we provide an iterative procedure to form the so‐called efficient coalition structure and we show that this coalition structure has the nice properties of being (i) weakly stable in the sense of the coalition structure core and (ii) strongly stable under a given assumption. An exact fractional programming based solution is also given to generate such efficient coalitions.     

Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs

In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time n ^o(k) in chordal and s-chordal (s>3) graphs unless W[1]=FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal and near chordal graphs. Our results prove that unless NP=P, the minimum dominating set in a chordal or s-chordal (s>3) graph cannot be approximated within a ratio of \fracc3lnn\frac{c}{3}\ln{n} in polynomial time, where n is the number of vertices in the graph and 0<c<1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar results for the Independent Dominating Set problem and the Connected Dominating Set problem in chordal or near chordal graphs.     

公众参与下政府与游戏企业发展策略的演化博弈分析

游戏企业选择设置防沉迷机制行为策略是应对青少年沉迷网络游戏等不良社会影响的有效举措，公众的监督和政府部门的监管是构建良好社会风气的重要保障。本文针对我国越来越多青少年沉迷虚拟网络游戏而影响社会风气的问题，考虑政府监管与公众的监督，构建政府、公众、游戏企业的三方演化博弈模型，并建立复制动态方程，得到不同情形下政府、公众和游戏企业的演化稳定策略；并通过数值分析的方法，分析监管成功率对政府与游戏企业防沉迷机制选择的影响。研究表明，监管成功率对游戏企业策略选择起着重要影响。不同情形下，政府可以根据所掌握的相关信息对游戏企业采取不同策略进行有效监管。从短期角度来看，无论政府采取何种策略，公众与游戏企业会考虑自身利益而选择"不监督"和"不设置防沉迷机制"；从长期角度来看，在没有政府监管情况下，公众与游戏企业依然会主动选择"监督"和"设置防沉迷机制"。     

Computing Supergame Equilibria

We present a general method for computing the set of supergame equilibria in infinitely repeated games with perfect monitoring and public randomization. We present a three‐stage algorithm that constructs a convex set containing the set of equilibrium values, constructs another convex set contained in the set of equilibrium values, and produces strategies that support them. We explore the properties of this algorithm by applying it to familiar games.     

An Approximation Algorithm for Alignment of Multiple Sequences using Motif Discovery

Given a set of N sequence, the Multiple Sequence Alignment problem is to align these N sequences, possibly with gaps, that brings out the best commonality of the N sequences. The quality of the alignment is usually measured by penalizing the mis-matches and gaps, and rewarding the matches with appropriate weight functions. However for larger values of N, additional constraints are required to give meaningful alignments. We identify a user-controlled parameter, an alignment number K (2 K N): this additional requirement constrains the alignment to have at least K sequences agree on a character, whenever possible, in the alignment. We identify a natural optimization problem for this approach called the K-MSA problem. We show that the problem is MAX SNP hard. We give a natural extension of this problem that incorporates biological relevance by using motifs (common patterns in the sequences) and give an approximation algorithm for this problem in terms of the motifs in the data. MUSCA is an implementation of this approach and our experimental results indicate that this approach is efficient, particularly on large numbers of long sequences, and gives good alignments when tested on biological data such as DNA and protein sequences.     

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.     

Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colorability

Hypergraph 2-colorability, also known as set splitting, is a widely studied problem in graph theory. In this paper we study the maximization version of the same. We recast the problem as a special type of satisfiability problem and give approximation algorithms for it. Our results are valid for hypergraph 2-colorability, set splitting and MAX-CUT (which is a special case of hypergraph 2-colorability) because the reductions are approximation preserving. Here we study the MAXNAESP problem, the optimal solution to which is a truth assignment of the literals that maximizes the number of clauses satisfied. As a main result of the paper, we show that any locally optimal solution (a solution is locally optimal if its value cannot be increased by complementing assignments to literals and pairs of literals) is guaranteed a performance ratio of . This is an improvement over the ratio of attributed to another local improvement heuristic for MAX-CUT (C. Papadimitriou, Computational Complexity, Addison Wesley, 1994). In fact we provide a bound of for this problem, where k 3 is the minimum number of literals in a clause. Such locally optimal algorithms appear to subsume typical greedy algorithms that have been suggested for problems in the general domain of satisfiability. It should be noted that the NAESP problem where each clause has exactly two literals, is equivalent to MAX-CUT. However, obtaining good approximation ratios using semi-definite programming techniques (M. Goemans and D.P. Williamson, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994a, pp. 422–431) appears difficult. Also, the randomized rounding algorithm as well as the simple randomized algorithm both (M. Goemans and D.P. Williamson, SIAM J. Disc. Math, vol. 7, pp. 656–666, 1994b) yield a bound of for the MAXNAESP problem. In contrast to this, the algorithm proposed in this paper obtains a bound of for this problem.     

On the power domination number of the generalized Petersen graphs

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. Following a set of rules for power system monitoring, a set S of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S. The minimum cardinality of a power dominating set of G is the power domination number γ _p (G). In this paper, we investigate the power domination number for the generalized Petersen graphs, presenting both upper bounds for such graphs and exact results for a subfamily of generalized Petersen graphs.     

Well paired-dominated graphs

A paired-dominating set is a dominating set whose induced subgraph contains at least one perfect matching. This could model the situation of guards or police where each has a partner or backup. We are interested in those where all “minimal” paired-dominating sets are the same cardinality. In this case, we consider “minimal” to be with respect to the pairings. That is, the removal of any two vertices paired under the matching results in a set that is not dominating. We give a structural characterization of all such graphs with girth at least eight.     

A {{10}}-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem

We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to its close relationship with minimum maximal matching; however, in the weighted case such a nice relationship is not known to exist. In this paper, after showing that weighted edge domination is as hard to approximate as the well studied weighted vertex cover problem, we consider a natural strategy, reducing edge-dominating set to edge cover. Our main result is a simple -approximation algorithm for the weighted edge-dominating set problem, improving the existing ratio, due to a simple reduction to weighted vertex cover, of 2r _WVC, where r _WVC is the approximation guarantee of any polynomial-time weighted vertex cover algorithm. The best value of r _WVC currently stands at . Furthermore we establish that the factor of is tight in the sense that it coincides with the integrality gap incurred by a natural linear programming relaxation of the problem.     

A heuristic approximation algorithm of minimum dominating set based on rough set theory

The minimum dominating set of graph has been widely used in many fields, but its solution is NP-hard. The complexity and approximation accuracy of existing algorithms need to be improved. In this paper, we introduce rough set theory to solve the dominating set of undirected graph. First, the adjacency matrix of undirected graph is used to establish an induced decision table, and the minimum dominating set of undirected graph is equivalent to the minimum attribute reduction of its induced decision table. Second, based on rough set theory, the significance of attributes (i.e., vertices) based on the approximate quality is defined in induced decision table, and a heuristic approximation algorithm of minimum dominating set is designed by using the significance of attributes (i.e., vertices) as heuristic information. This algorithm uses forward and backward search mechanism, which not only ensures to find a minimal dominating set, but also improves the approximation accuracy of minimum dominating set. In addition, a cumulative strategy is used to calculate the positive region of induced decision table, which effectively reduces the computational complexity. Finally, the experimental results on public datasets show that our algorithm has obvious advantages in running time and approximation accuracy of the minimum dominating set.

     

Approximation hardness of edge dominating set problems

We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, MINIMUM EDGE DOMINATING SET and MINIMUM MAXIMAL MATCHING. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than . The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs. An extended abstract of this paper was accepted at the 14th Annual International Symposium on Algorithms and Computation, ISAAC 2003.