Column Subset Selection Problem is UG-hard

We address two problems related to selecting an optimal subset of columns from a matrix. In one of these problems, we are given a matrix A∈R^m×n$A\in {\mathbb{R}}^{m\times n}$ and a positive integer k, and we want to select a sub-matrix C of k   columns to minimize _{‖A−ΠCA‖F}${\Vert A-{\Pi }_{C}A\Vert }_F$, where _ΠC=CC⁺${\Pi }_C=C{C}^{+}$ denotes the matrix of projection onto the space spanned by C  . In the other problem, we are given A∈R^m×n$A\in {\mathbb{R}}^{m\times n}$, positive integers c and r, and we want to select sub-matrices C and R of c columns and r rows of A  , respectively, to minimize _{‖A−CUR‖F}${\Vert A-CUR\Vert }_F$, where U∈R^c×r$U\in {\mathbb{R}}^{c\times r}$ is the pseudo-inverse of the intersection between C and R. Although there is a plethora of algorithmic results, the complexity of these problems has not been investigated thus far. We show that these two problems are NP-hard assuming UGC.     

A Hard Dial-a-Ride Problem that is Easy on Average

In the dial-a-ride-problem (Darp) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find the shortest transportation for the server. We study the Darp when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm that finds an optimal solution with high probability. Moreover, with high probability the optimality of the solution found can be certified efficiently. In addition, we examine the complexity of the Darp in a semirandom setting and in the unweighted case.Research supported by the German Science Foundation (DFG, grant FOR 413/1-1)Research supported by the German Science Foundation (DFG, grant Gr 883/10)Research supported by the German Science Foundation (DFG, grant PR 296/6-3)     

Graph fragmentation problem: analysis and synthesis

Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst‐case analysis of a random attack. We can choose a fixed number of individuals for protection, and a nonprotected target node immediately destroys all reachable nodes. The goal is to minimize the expected number of destroyed nodes in the network. In this paper, we address the GFP by several approaches: metaheuristics, approximation algorithms, polytime methods for specific instances, and exact methods for small instances. The computational complexity of the GFP is included in our analysis, where we formally prove that the corresponding decision version of the problem is ‐complete. Furthermore, a strong inapproximability result holds: there is no polynomial approximation algorithm with factor lower than 5/3, unless . This promotes the study of specific instances of the problem for tractability and/or exact methods in exponential time. As a synthesis, we propose new vulnerability/connectivity metrics and an interplay with game theory using a closely related combinatorial problem called component order connectivity.     

Extreme time-space tradeoffs for graphs with small space requirements

Two new isometric array languages, called Linear Array Languages (LAL) and Extended Regular Array Languages (ERAL), are introduced. A more abundant hierarchy for isometric languages is established. We show that some properties of two-dimensional array patterns do not coincide with their one-dimensional counterparts.     

工厂地址集中的k-种产品选址问题的近似算法

k-种产品工厂选址问题是：给定一个客户集合和一个可以建立工厂的地址集合,每个客户需要k-种产品,一个工厂只能为客户提供一种产品。考虑的工厂假设相对集中,即假设任何工厂之间的距离都不大于工厂与客户之间的距离。对于没有建厂费用的问题,当k=2时证明了它是一个NP完全问题,对任意的k给出了一个最坏性能比不大于2-1/k的近似算法。对于有建厂费用的问题,给出了一个最坏性能比不大于2的近似算法。     

基于博弈论的域间组播计费模型

实用的组播计费机制是IP组播能够在域间得以广泛部署的前提条件.从不同参与者的角度讨论了IP组播的3种典型的服务模型及其相应的可实施的计费策略.这3种模型代表了域间组播的多种可能情况,它们是ICP-USER模型、ICP-ISP模型以及ICP-ISP-USER模型.分析了每种模型所对应的应用场景、解决方案以及提出算法的复杂性等.整个Internet被看作是一个生态系统,该工作利用博弈论的思想,尊重各个参与者的目的和利益,使得Internet的自组织特性得以充分体现,有利于Internet中"生态链"的长期、稳定和健康发展,具有很好的实用性.     

基于物品移动的局内装箱算法的改进

局内装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用.提出一个新的局内线性算法MAMOV, 算法中采用"物品移动模型",当新物品到达时,允许首次入箱后的固定数目的物品再次移动;证明MAMOV算法的最坏情况渐近性能比1.25,该算法最坏情况渐近性能比低于同类算法最坏情况渐近性能比的下界值.     

Parameterized Computation and Complexity： A New Approach Dealing with NP-Hardness

The theory of parameterized computation and complexity is a recently developed subarea in theoretical computer science. The theory is aimed at practically solving a large number of computational problems that are theoretically intractable.The theory is based on the observation that many intractable computational problems in practice are associated with a parameter that varies within a small or moderate range. Therefore, by taking the advantages of the small parameters, many theoretically intractable problems can be solved effectively and practically. On the other hand, the theory of parameterized computation and complexity has also offered powerful techniques that enable us to derive strong computational lower bounds for many computational problems, thus explaining why certain theoretically tractable problems cannot be solved effectively and practically. The theory of parameterized computation and complexity has found wide applications in areas such as database systems, programming languages, networks, VLSI design, parallel and distributed computing, computational biology, and robotics. This survey gives an overview on the fundamentals, algorithms, techniques, and applications developed in the research of parameterized computation and complexity. We will also report the most recent advances and excitements, and discuss further research directions in the area.     

Competitive Cloud Pricing for Long-Term Revenue Maximization

Journal of Computer Science and Technology - We study the pricing policy optimization problem for cloud providers while considering three properties of the real-world market: 1) providers have only...     

Approximation Algorithms for 3D Orthogonal Knapsack

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 ε and 8 ε , as well as an algorithm with approximation ratio 7 ε that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 ε and 5 ε , respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.     

Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs

The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ε > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (ku, kl), our algorithm constructs a vertex cover of size (ku*, kl* ), satisfying max{ku*/ku, kl* /kl} 1 ε.     

Competitive Pricing Strategies for Software and SaaS Products

We study the pricing strategies for a software firm and an entrant software-as-a-service (SaaS) firm in two customer markets: the market composed of the incumbent’s past customers and the market of new customers. We build a game theoretical model to investigate how user costs and the quality differential between products affect firms’ pricing in different customer markets. Our findings show that it is not always optimal for the software firm to price discriminate between its old users and the new customers. The entrant firm would be better off acquiring only the new customers when the SaaS quality is sufficiently low.     

具有多优先级多服务网络的激励价格控制

运用Stackelberg对策中的激励原理,研究具有多优先级的多服务网络系统的价控问题。提出了具有管理者的用户两优先级的激励模型,给出了确定激励参数的方法。将此方法扩展到多优先级的情形,推导出互联激励参数矩阵。通过数值例子说明了激励价格策略的有效性。     

互联网通信中的信息选取与分布问题的建模与求解

讨论了互联网通信中的一个信息选取与规划问题。由于内部网的单个Web服务器容量不够大,不能容纳与日剧增的信息内容,如何将众多的信息分布到多个Web服务器上,使得每个服务器上存放的信息总量不超过各个服务器容量且避免访问瓶颈的发生;这是陈卫东等1999年提出的一个新问题,该文建立了该问题的一个优化新模型,在讨论了它的强NP－完全性,难近似性后,给出了一个伪多项式时间最优算法的一个多项式时间近似算法。     

Hardness and methods to solve CLIQUE

The paper briefly reviews NP-hard optimization problems and their inapproximability.The hardness of solving CLIQUE problem is specifically discussed.A dynamic-programming algorithm and its improved version for CLIQUE are reviewed and some additional analysis is presented.The analysis implies that the improved algorithm.HEWN(hierarchical edge-weighted network),only provides a heuristic or useful method,but cannot be called a polynomial algorithm.     

Design and Performance Evaluation of Sequence Partition Algorithms

Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of n distinct numbers into minimum number of monotone （increasing or decreasing） subsequences. This problem is NP-hard and the number of monotone subsequences can reach [√2n＋1/1-1/2]in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than [√2n＋1/1-1/2]monotone subsequences in O（n^1.5） time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity O（n^3）, a known greedy algorithm of time complexity O（n^1.5 log n）, and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.     

Parameterized pursuit-evasion games

We study the parameterized complexity of four variants of pursuit-evasion on graphs: Seeded Pursuit Evasion, Short Seeded Pursuit Evasion, Directed Pursuit Evasion and Short Directed Pursuit Evasion. Both Seeded Pursuit Evasion and Short Seeded Pursuit Evasion are played on undirected graphs with given starting positions for both the cops and the robber. Directed Pursuit Evasion and its short variant are played on directed graphs, with the players free to choose their starting positions. We show for Seeded Pursuit Evasion and Directed Pursuit Evasion that finding a winning strategy for the cops is AW[*]-hard when we parameterize by the number of cops. Further, we show that the short (k-move) variants of these problems (Short Seeded Pursuit Evasion and Short Directed Pursuit Evasion) are AW[*]-complete when we parameterize by both the number of cops and turns.     

Multi‐Unit Bayesian Auction with Demand or Budget Constraints

We consider the problem of revenue maximization on multi‐unit auctions where items are distinguished by their relative values; any pair of items has the same ratio of values to all buyers. As is common in the study of revenue maximizing problems, we assume that buyers' valuations are drawn from public known distributions and they have additive valuations for multiple items. Our problem is well motivated by sponsored search auctions, which made money for Google and Yahoo! in practice. In this auction, each advertiser bids an amount b_i to compete for ad slots on a web page. The value of each ad slot corresponds to its click‐through‐rate, and each buyer has her own per‐click valuations, which is her private information. Obviously, a strategic bidder may bid an amount that is different with her true valuation to improve her utility. Our goal is to design truthful mechanisms avoiding this misreporting. We develop the optimal (with maximum revenue) truthful auction for a relaxed demand model (where each buyer i wants at most d_i items) and a sharp demand model (where buyer i wants exactly d_i items). We also find an auction that always guarantees at least half of the revenue of the optimal auction when the buyers are budget constrained. Moreover, all of the auctions we design can be computed efficiently, that is, in polynomial time.