检索结果-内蒙古大学图书馆

(2P2,K4)-FREE GRAPHS ARE 4-COLORABLE

SIAM JOURNAL ON DISCRETE MATHEMATICS 2019年第2期33卷 1095-1120页

作者： Gaspers, Serge Huang, Shenwei UNSW Sydney Sch Comp Sci & Engn Sydney NSW 2052 Australia CSIRO Data61 Decis Sci Sydney NSW 2052 Australia Nankai Univ Coll Comp Sci Tianjin 300350 Peoples R China

In this paper, we show that every (2P(2), K-4)-free graph is 4-colorable. The bound is attained by the five-wheel and the complement of the seven-cycle. This answers an open question by Wagon [J. Combin. Theory Ser. B, 29 (1980), pp. 345{346] from the 1980s. Our result can also be viewed as a result in the study of the Vizing bound for graph classes. A major open problem in the study of computational complexity of graph coloring is whether coloring can be solved in polynomial time for (4P(1), C-4)-free graphs. Lozin and Malyshev [Discrete Appl. Math., 216 (2017), pp. 273{280] conjecture that the answer is yes. As an application of our main result, we provide the first positive evidence to the conjecture by giving a 2-approximation algorithm for coloring (4P(1), C-4)-free graphs.

关键词： graph coloring chi-bound forbidden induced subgraphs approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Linearly χ-bounding (P6, C4)-free graphs

引用

JOURNAL OF GRAPH THEORY 2019年第3期92卷 322-342页

作者： Gaspers, Serge Huang, Shenwei UNSW Sydney Sch Comp Sci & Engn Sydney NSW Australia CSIRO Data61 Decis Sci Sydney NSW Australia Nankai Univ Coll Comp Sci Tianjin 300071 Peoples R China

Given two graphs H-1 and H-2, a graphG is (H-1, H-2)-free if it contains no induced subgraph isomorphic to H-1 or H-2. Let P-t and C-s be the path on t vertices and the cycle on s vertices, respectively. In this paper we show that for any (P-6, C-4)-free graph G it holds that chi(G) <= (3/2)omega(G), where chi(G) and omega(G) are the chromatic number and clique number of G, respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all 4-critical (P-6, C-4)-free graphs other than K-4 (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211-232]). The new result unifies previously known results on the existence of linear chi-binding functions for several graph classes. Our proof is based on a novel structure theorem on (P-6, C-4)-free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time 3/2-approximation algorithm for coloring (P-6, C-4)-free graphs. Our algorithm computes a coloring with (3/2)omega(G) colors for any (P-6, C-4)-free graph G in O(n(2)m) time.

关键词： approximation algorithm forbidden induced subgraphs graph coloring linear chi-bound structure theorem

来源：评论

学校读者我要写书评

暂无评论

Uncertain about your travel plan? Lock it and decide later: Dynamic pricing with a fare-lock option

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2019年 125卷 1-26页

作者： Chen, Ming Chen, Zhi-Long Calif State Univ Long Beach Coll Business Long Beach CA 90840 USA Univ Maryland Robert H Smith Sch Business College Pk MD 20742 USA

Some airlines now offer fare-lock options, which allow passengers to hold a ticket for some time with a small fee while finalizing their travel plans. In this paper, we model passenger behavior in the presence of a fare-lock option and study the corresponding airline's dynamic pricing problem. We prove some monotonicity properties and generate a number of managerial insights on possible implications of the fare-lock option on the airline's revenue and optimal pricing structure, the social welfare, and the passenger surplus. We also develop an approximation algorithm that is capable of generating near-optimal solutions for large problem instances quickly.

关键词： Revenue management Dynamic pricing Fare-lock option Dynamic programming approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets

引用

DISCRETE APPLIED MATHEMATICS 2019年 257卷 101-114页

作者： Dannenberg, Katharina Jansson, Jesper Lingas, Andrzej Lundell, Eva-Marta Univ Lubeck Inst Theoret Comp Sci Ratzeburger Allee 160 D-23562 Lubeck Germany Univ Lubeck Grad Sch Comp Med & Life Sci Ratzeburger Allee 160 D-23562 Lubeck Germany Hong Kong Polytech Univ Dept Comp Hung Hom Kowloon Hong Kong Peoples R China Lund Univ Dept Comp Sci Box 118 S-22100 Lund Sweden

The NP-hard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set S of leaf labels and a set R. of resolved triplets over S and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in R. This article studies the approximability of a generalization of the problem called the maximum rooted triplets consistency problem (MTC) where in addition to resolved triplets, the input may contain fan triplets, forbidden resolved triplets, and forbidden fan triplets. To begin with, we observe that MTC admits a 1/4-approximation in polynomial time. Next, we generalize Wu's exact exponential-time algorithm for MRTC (Wu, 2004) to MTC. Forcing the algorithm to always output a rooted k-ary phylogenetic tree for any specified k >= 2 subsequently leads to an exponential-time approximation scheme (ETAS) for MTC. We then present a polynomial time approximation scheme (PTAS) for complete instances of MTC (meaning that for every S'subset of S with vertical bar S'vertical bar= 3, R contains at least one rooted triplet involving the leaf labels in S'), based on the techniques introduced by Jiang et al. (2001) for a related problem. We also study the computational complexity of MTC restricted to fan triplets and forbidden fan triplets. Finally, extensions to weighted instances are considered. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Phylogenetic tree Rooted triplet approximation algorithm Dynamic programming Smooth polynomial integer program

来源：评论

学校读者我要写书评

暂无评论

A market-oriented incentive mechanism for emergency demand response in colocation data centers

引用

SUSTAINABLE COMPUTING-INFORMATICS & SYSTEMS 2019年 22卷 13-25页

作者： Wang, Youshi Zhang, Fa Chi, Ce Ren, Shaolei Liu, Fangming Wang, Rui Liu, Zhiyong Chinese Acad Sci Inst Comp Technol High Performance Comp Res Ctr Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China Univ Calif Riverside Riverside CA 92521 USA Huazhong Univ Sci & Technol Wuhan Hubei Peoples R China Microsoft Beijing Peoples R China

Rapidly developing colocation data centers (or colocations, for short) have become important participants in emergency demand response (EDR) programs. Different from traditional data centers, in colocations, tenants control their own servers;thus, they may not coordinate to reduce their power consumption. In this paper, to encourage tenants to join EDR programs, we propose a market-oriented incentive mechanism, MicDR, which can effectively reduce energy costs. MicDR includes a local incentive mechanism (LiMec), a global incentive mechanism (GiMec) and a server-sharing incentive mechanism (SiMec). LiMec motivates tenants to improve their energy efficiency locally. GiMec encourages tenants to improve their energy efficiency by requesting public server resources. To support the requests sparked by GiMec, SiMec encourages tenants to share idle server resources. A (1 + epsilon)-approximation algorithm is proposed to achieve an asymptotic optimal energy-saving scheme. The performance of the proposed algorithm is evaluated, and trace-driven simulations verify the effectiveness and feasibility of MicDR. (C) 2019 Elsevier Inc. All rights reserved.

关键词： approximation algorithm Colocation data center Energy efficiency Incentive mechanism Truthfulnessa

来源：评论

学校读者我要写书评

暂无评论

Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines

引用

BULLETIN OF THE POLISH ACADEMY OF SCIENCES-TECHNICAL SCIENCES 2019年第1期67卷 31-36页

作者： Pikies, T. Kubale, M. Gdansk Univ Technol ETI Fac Dept Algorithms & Syst Modelling Gabriela Narutowicza 11-12 PL-80233 Gdansk Poland

The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is algorithm 2 which is 2-approximate for the problem Qm vertical bar p(j) =1,G = bisubquartic vertical bar C-max. The second one is algorithm 3 which is 4-approximate for the problem Qm vertical bar p(j) =1,G = bisubquarticl vertical bar Sigma C-j, where m is an element of {2, 3, 4). The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width, and on the properties of ideal machine, an abstract machine that we introduce in this paper.

关键词： approximation algorithm graph coloring incompatible job polynomial algorithm scheduling uniform machine unit-time job

来源：评论

学校读者我要写书评

暂无评论

Recommending links through influence maximization

引用

THEORETICAL COMPUTER SCIENCE 2019年 764卷 30-41页

作者： D'Angelo, Gianlorenzo Severini, Lorenzo Velaj, Yllka GSSI Viale F Crispi 7 I-67100 Laquila Italy ISI Fdn Via Chisola 5 I-10126 Turin Italy Univ G dAnnunzio Viale Pindaro 20 I-65127 Pescara Italy

The link recommendation problem consists in suggesting a set of links to the users of a social network in order to increase their social circles and the connectivity of the network. Link recommendation is extensively studied in the context of social networks and of general complex networks due to its wide range of applications. Most of the existing link recommendation methods estimate the likelihood that a link is adopted by users and recommend links that are likely to be established. However, most of such methods overlook the impact that the suggested links have on the capability of the network to spread information. Indeed, such capability is directly correlated with both the engagement of a single user and the revenue of online social networks. In this paper, we study link recommendation systems from the point of view of information diffusion. In detail, we consider the problem in which we are allowed to spend a given budget to create new links so to suggest a bounded number of possible persons to whom become friend in order to maximize the influence of a given set of nodes. We model the influence diffusion in a network with the popular Independent Cascade model. (C) 2018 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Information diffusion Complex networks Independent cascade model Network augmentation

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling with job-dependent machine deterioration

引用

JOURNAL OF SCHEDULING 2019年第6期22卷 691-707页

作者： Luo, Wenchang Xu, Yao Tong, Weitian Lin, Guohui Ningbo Univ Sch Math & Stat Ningbo 315211 Zhejiang Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Georgia Southern Univ Dept Comp Sci Statesboro GA 30460 USA

We consider the single-machine scheduling problem with job-dependent machine deterioration. In the problem, we are given a single machine with an initial nonnegative maintenance level, and a set of jobs each with a non-preemptive processing time and a machine deterioration. Such a machine deterioration quantifies the decrement in the machine maintenance level after processing the job. To avoid a machine breakdown, one should guarantee a nonnegative maintenance level at any time point, and whenever necessary, a maintenance activity must be allocated for restoring the machine maintenance level. The goal of the problem is to schedule the jobs and the maintenance activities such that the total completion time of jobs is minimized. There are two variants of maintenance activities: In the partial maintenance case, each activity can be allocated to increase the machine maintenance level to any level not exceeding the maximum;in the full maintenance case, every activity must be allocated to increase the machine maintenance level to the maximum. In a recent work, the problem in the full maintenance case was proven NP-hard;several special cases of the problem in the partial maintenance case were shown to be solvable in polynomial time, but the complexity of the general problem was left open. In this paper we first prove that the problem in the partial maintenance case is binary NP-hard, thus settling the open problem;we then design a 2-approximation algorithm and a branch-and-bound exact search algorithm. Computational experiments are conducted for the two algorithms to examine their practical performance.

关键词： Scheduling Machine deterioration Maintenance Binary NP-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Permutation flowshop scheduling with simple linear deterioration

引用

ENGINEERING OPTIMIZATION 2019年第8期51卷 1281-1300页

作者： Sun, Lin-Hui Ge, Chen-Chen Zhang, Wei Wang, Ji-Bo Lu, Yuan-Yuan Xian Univ Sci & Technol Sch Management Xian Shaanxi Peoples R China Xian Univ Sci & Technol Sch Management Lean Prod & Human Engn Res Ctr Xian Shaanxi Peoples R China Shenyang Aerosp Univ Sch Sci Shenyang Liaoning Peoples R China Jilin Normal Univ Coll Math Siping Peoples R China

This article addresses permutation flowshop scheduling problems with simple linear deterioration. The objectives are to minimize logarithm of the makespan, total logarithm of the completion time, total weighted logarithm of the completion time, and the sum of the quadratic job logarithms of the completion times. approximation algorithms and their worst-case bounds are presented and analysed. Branch-and-bound algorithms are also proposed to solve the problems optimally. Computational experiments are performed to illustrate the algorithms.

关键词： Scheduling deteriorating job flowshop worst-case bound approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Vertex cover in conflict graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 774卷 103-112页

作者： Miao, Dongjing Liu, Xianmin Li, Yingshu Li, Jianzhong Harbin Inst Technol Harbin 150001 Heilongjiang Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

We study a graph class called conflict graph, which is a union of a finite number of given forests of complete multipartite graph. It is interesting that conflict graph can model many natural problems, such as in database application and others. We show that this property is non-trivial if limiting the number of forests of complete multipartite graph. Then study the problem of vertex cover on conflict graph in this paper. The results list as follows, if the number of forests of complete multipartite graph is fixed, conflict graph is non-trivial property, but finding 1.36-approximation algorithms is NP-hard. Also given 2 forests of complete multipartite graph and maximum degree less than 7, vertex cover problem of conflict graph is NP-complete. Moreover, it is shown to be NP-hard to find an algorithm for vertex cover of conflict graph within 41/40 - epsilon, for any epsilon > 0, if there is no the degree restriction over the graph. At last, we design an approximation algorithm for the conflict graph consisting of r forests of complete multipartite graph and show that the approximation ratio can be bounded by 2 - 1/2(r) and it's near optimal. (C) 2016 Published by Elsevier B.V.

关键词： approximation algorithm Vertex cover Complete multipartite graph Graph coloring

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：