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

23rd International Computing and Combinatorics Conference (COCOON)

作者： Chen, Zhi-Zhong Lin, Guohui Wang, Lusheng Chen, Yong Wang, Dan Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada City Univ Hong Kong Dept Comp Sci 83 Tat Chee Ave Kowloon Hong Kong Peoples R China City Univ Hong Kong Shenzhen Res Inst Shenzhen Hitech Ind Pk Shenzhen Peoples R China Hangzhou Dianzi Univ Inst Operat Res & Cybernet Hangzhou 310018 Zhejiang Peoples R China

ISBN: (纸本)9783319623887

Given a vertex-weighted connected graph G=(V,E), the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio of 13 / 17. The currently best approximation algorithm for MwIST only has a performance ratio of 1/3-E, for any E>0. In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm.

关键词： Maximum weight internal spanning tree Maximum weight matching approximation algorithm Performance analysis

来源：评论

学校读者我要写书评

暂无评论

STATISTICAL MATCHING AND SUBCLASSIFICATION WITH A CONTINUOUS DOSE: CHARACTERIZATION, algorithm, AND APPLICATION TO A HEALTH OUTCOMES STUDY

引用

ANNALS OF APPLIED STATISTICS 2023年第1期17卷 454-475页

作者： Zhang, B. O. Mackay, Emily J. Baiocchi, M. I. K. E. Fred Hutchinson Canc Ctr Vaccine & Infect Dis Div Seattle WA 98109 USA Univ Penn Perelman Sch Med Dept Anesthesiol & Crit Care Philadelphia PA USA Stanford Univ Dept Epidemiol & Populat Hlth Stanford CA USA

Subclassification and matching are often used in empirical studies to adjust for observed covariates;however, they are largely restricted to rela-tively simple study designs with a binary treatment and less developed for designs with a continuous exposure. Matching with exposure doses is partic-ularly useful in instrumental variable designs and in understanding the dose -response relationships. In this article we propose two criteria for optimal sub-classification based on subclass homogeneity, in the context of having a con-tinuous exposure dose, and propose an efficient polynomial-time algorithm that is guaranteed to find an optimal subclassification with respect to one criterion and serves as a 2-approximation algorithm for the other criterion. We discuss how to incorporate dose and use appropriate penalties to control the number of subclasses in the design. Via extensive simulations, we sys-tematically compare our proposed design to optimal nonbipartite pair match-ing and demonstrate that combining our proposed subclassification scheme with regression adjustment helps to reduce model dependence for paramet-ric causal inference with a continuous dose. We apply the new design and associated randomization-based inferential procedure to study the effect of transesophageal echocardiography (TEE) monitoring during coronary artery bypass graft (CABG) surgery on patients' postsurgery clinical outcomes, us-ing Medicare and Medicaid claims data, and find evidence that TEE monitor-ing lowers patients' all-cause 30-day mortality rate.

关键词： approximation algorithm continuous dose dose-response relationship edge cover full match subclassification

来源：评论

学校读者我要写书评

暂无评论

algorithms for Right-sizing Heterogeneous Data Centers

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2023年第4期10卷 1-28页

作者： Albers, Susanne Quedenfeld, Jens Tech Univ Munich Boltzmannstr 3 D-85748 Garching Germany

Power consumption is a dominant and still growing cost factor in data centers. In time periods with low load, the energy consumption can be reduced by powering down unused servers. We resort to a model introduced by Lin, Wierman, Andrew, and Thereska [23, 24] that considers data centers with identical machines and generalize it to heterogeneous data centers with d different server types. The operating cost of a server depends on its load and is modeled by an increasing, convex function for each server type. In contrast to earlier work, we consider the discrete setting, where the number of active servers must be integral. Thereby, we seek truly feasible solutions. For homogeneous data centers (d = 1), both the offline and the online problem were solved optimally in References [3, 4]. In this article, we study heterogeneous data centers with general time-dependent operating cost functions. We develop an online algorithm based on a work function approach that achieves a competitive ratio of 2d + 1 +. for any. > 0. For time-independent operating cost functions, the competitive ratio can be reduced to 2d + 1. There is a lower bound of 2d shown in Reference [5], so our algorithm is nearly optimal. For the offline version, we give a graph-based ( 1+.)-approximation algorithm. Additionally, our offline algorithm is able to handle time-variable data-center sizes.

关键词： Heterogeneous machines energy conservation online algorithm competitive analysis approximation algorithm discrete setting

来源：评论

学校读者我要写书评

暂无评论

Total 2-Rainbow Domination in Graphs: Complexity and algorithms

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2023年第07期35卷 887-906页

作者： Kumar, Manjay Reddy, P. Venkata Subba Natl Inst Technol Warangal Dept Comp Sci & Engn Warangal 506004 Telangana India

For a simple, undirected graph G(V,E) without isolated vertices, a function h : V -> {phi, {1}, {2}, {1, 2}} which satisfies the following two conditions is called a total 2-rainbow dominating function (T2RDF) of G. (i) For all u is an element of V, if h(u) = phi then boolean OR(v is an element of N(u))h(v) = {1, 2} and (ii) Every u is an element of V with h(u) not equal phi is adjacent to a vertex v with h(v) not equal phi. The weight of a T2RDF h of G is the value h(V) = Sigma(u is an element of V) vertical bar h(u)vertical bar. The total 2-rainbow domination number is the minimum weight of a T2RDF on G and is denoted by gamma(tr2)(G). The minimum total 2-rainbow domination problem (MT2RDP) is to find a T2RDF of minimum weight in the input graph. In this article, we show that the problem of deciding if G has a T2RDF of weight at most l for star convex bipartite graphs, comb convex bipartite graphs, split graphs and planar graphs is NP-complete. On the positive side, we show that MT2RDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, we show that MT2RDP cannot be approximated within (1 - epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless P = NP and also propose 2(ln(Delta algorithm for it. Further, we show that MT2RDP is APX-complete for graphs with maximum degree 4. Next, it is shown that domination problem and the total 2-rainbow domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming formulation for MT2RDP is presented.

关键词： Domination total 2-rainbow domination graph classes NP-complete approximation algorithm APX-complete integer linear programming

来源：评论

学校读者我要写书评

暂无评论

1-Line Minimum λ-Steiner Tree Problem 42nd

1-Line Minimum λ-Steiner Tree Problem

引用

42nd National Conference on Theoretical Computer Science

作者： Chen, Yinhua Li, Jianglin Wang, Wencheng Zhang, Tongquan Yunnan Minzu Univ Sch Math & Comp Sci Yuehua St 2929 Kunming 650504 Yunnan Peoples R China Yunnan Minzu Univ Sch Appl Technol Yuehua St 2929 Kunming 650504 Yunnan Peoples R China

ISBN: (纸本)9789819614899;9789819614905

In this paper, we consider the problem of 1-line minimum lambda-Steiner tree problem, denoted as the 1L-M(lambda)StT problem. Given a set X = {r(1), r(2),..., r(n)} of n points in the lambda-plane and a straight line l in R-2, we need to construct a Steiner tree T-l connecting the n points in X and the straight line l. The objective is to minimize the total cost of such a Steiner tree T-l, i.e.,min{Sigma(epsilon is an element of Tl) w(e) | T-l is the mentioned Steiner tree}, and if an edge e = uv is an element of T-l has both endpoints u and v lying on the line l, the weight is defined as w(e) = 0;Otherwise, it is defined as the distance of the two endpoints u and v in the lambda-plane. In particular, if all Steiner points in T-l are constrained to lie on the line l, the problem is denoted as the 1-line minimum lambda-spanning tree (1L-M lambda ST) problem. We present two main results. (1) By using the strategies of the sweep-line algorithm, we can design an exact algorithm in time O(lambda n log n) to solve the 1L-M lambda ST problem;(2) Using some properties of lambda-plane, we showed that our algorithm is a rho(lambda)-approximation algorithm for the 1L-M(lambda)StT problem, where rho(lambda) is inverse of the Steiner ratio in the lambda-plane.

关键词： Sweep-line algorithm approximation algorithm 1-line lambda-spanning tree 1-line lambda-Steiner tree

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Minimum Norm and Ordered Optimization Problems 2019

Approximation Algorithms for Minimum Norm and Ordered Optimi...

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Chakrabarty, Deeparnab Swamy, Chaitanya Dartmouth Hanover NH 03755 USA Univ Waterloo Waterloo ON Canada

ISBN: (纸本)9781450367059

In many optimization problems, a feasible solution induces a multidimensional cost vector. For example, in load-balancing a schedule induces a load vector across the machines. In k-clustering, opening k facilities induces an assignment cost vector across the clients. Typically, one seeks a solution which either minimizes the sum- or the max- of this vector, and these problems (makespan minimization, k-median, and k-center) are classic NP-hard problems which have been extensively studied. In this paper we consider the minimum-norm optimization problem. Given an arbitrary monotone, symmetric norm, the problem asks to find a solution which minimizes the norm of the induced cost-vector. Such norms are versatile and include l(p) norms, Top-l norm (sum of the l largest coordinates in absolute value), and ordered norms (non-negative linear combination of Top- l norms), and consequently, the minimum-norm problem models a wide variety of problems under one umbrella, We give a general framework to tackle the minimum-norm problem, and illustrate its efficacy in the unrelated machine load balancing and k-clustering setting. Our concrete results are the following. (a) We give constant factor approximation algorithms for the minimum norm load balancing problem in unrelated machines, and the minimum norm k-clustering problem. To our knowledge, our results constitute the first constant-factor approximations for such a general suite of objectives. (b) For load balancing on unrelated machines, we give a (2 + epsilon)-approximation for ordered load balancing (i.e., min-norm loadbalancing under an ordered norm). (c) For k-clustering, we give a (5 + epsilon)-approximation for the ordered k-median problem, which significantly improves upon the previous-best constant-factor approximation (Chakrabarty and Swamy (ICALP 2018);Byrka, Sornat, and Spoerhase (STOC 2018)). (d) Our techniques also implyO(1) approximations to the instancewise best simultaneous approximation factor for unrelated-mac

关键词： approximation algorithm minimum norm optimization ordered optimization clustering load balancing

来源：评论

学校读者我要写书评

暂无评论

approximation and Polynomial algorithms for Multi-depot Capacitated Arc Routing Problems 22nd

Approximation and Polynomial Algorithms for Multi-depot Capa...

引用

22nd International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2021)

作者： Yu, Wei Liao, Yujie East China Univ Sci & Technol Sch Math Shanghai 200237 Peoples R China

ISBN: (纸本)9783030967727;9783030967710

We study the multi-depot capacitated arc routing problem (MCARP), which generalizes the classical arc routing problem to the more realistic situation with multiple depots. We propose approximation and polynomial algorithms for different variants of the MCARP. First, we present the first constant-factor approximation algorithms for the MCARP and the nonfixed destination variant. Second, for a restricted case of the MCARP with infinite vehicle capacity, called the multi-depot rural postman problem, we devise a (2 - 1/2k+1)-approximation algorithm with k indicating the number of depots. Lastly, we show that the equal-demand MCARP defined on a line graph is polynomially solvable and develop a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line.

关键词： approximation algorithm Multi-depot Vehicle routing problem Arc routing problem Rural postman problem

来源：评论

学校读者我要写书评

暂无评论

Approximating Branchwidth on Parametric Extensions of Planarity 50th

Approximating Branchwidth on Parametric Extensions of Planar...

引用

50th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Thilikos, Dimitrios M. Wiederrecht, Sebastian Univ Montpellier CNRS LIRMM Montpellier France Inst for Basic Sci Korea Daejeon South Korea

ISBN: (纸本)9783031754081;9783031754098

The branchwidth of a graph has been introduced by Roberson and Seymour as a measure of the tree-decomposability of a graph, alternative to treewidth. Branchwidth is polynomially computable on planar graphs by the celebrated "Ratcatcher"-algorithm of Seymour and Thomas. We investigate an extension of this algorithm to minor-closed graph classes, further than planar graphs, as follows: Let H-1 be a graph embeddable in the torus and H-2 be a graph embeddable in the projective plane. We prove that every {H-1, H-2}-minor free graph G contains a subgraph G' where the difference between the branchwidth of G and the branchwidth of G' is bounded by some constant, depending only on H-1 and H-2. Moreover, the graph G' admits a tree decomposition where all torsos are planar. This decomposition can be used for deriving a constant-additive approximation for branchwidth: For {H-1, H-2}- minor free graphs, there is a constant c (depending on H-1 and H-2) and an O(vertical bar V (G)vertical bar(3))-time algorithm that, given a graph G, outputs a value b such that the branchwidth of G is between b and b + c.

关键词： Branchwidth Tree decomposition Tangle Slope approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Mitigate the Damage of Rumor on Susceptible Group 35th

Mitigate the Damage of Rumor on Susceptible Group

引用

35th Australasian Database Conference

作者： Tang, Yao Wang, Jinghao Chen, Chen Wang, Xiaoyang Zhang, Wenjie Zhang, Ying Zhejiang Congshang Univ Hangzhou Peoples R China Univ Technol Sydney Ultimo Australia Univ Wollongong Wollongong NSW Australia Univ New South Wales Sydney NSW Australia

ISBN: (纸本)9789819612413;9789819612420

Rumor Blocking (RB) aims to identify a certain number of seed nodes that spread positive information to suppress the spread of rumor nodes in social networks. However, RB only considers the number of nodes to be protected but does not specifically consider protecting the susceptible group, which has a high probability of exposure to rumors. To fill this gap, in this paper, we propose a new notion of Truth Score (TS) that captures the degree of rumor mitigation for susceptible group. On this basis, we propose the Truth Score Maximization (TSM) problem, whose goal is to find a truth campaign seed set with budget k so as to maximize its TS. We prove that TSM is NP-hard and its objective function is monotonic but non-submodular. To solve the problem, we first derive submodular lower and upper bounding functions for our objective. Then, a general framework is proposed, which offers (1 - 1/e - epsilon)-approximation for maximizing the proposed bounding functions. Combining these two approximation algorithms, our final solution for TSM provides a data-dependent approximation guarantee. Finally, we conduct experiments on real-world social networks to demonstrate the efficiency and effectiveness of the proposed algorithm.

关键词： Rumor Blocking NP-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

View-based Explanations for Graph Neural Networks (Extended Abstract) 40

View-based Explanations for Graph Neural Networks (Extended ...

引用

40th International Conference on Data Engineering Workshop (ICDEW)

作者： Chen, Tingyang Qiu, Dazhuo Wu, Yinghui Khan, Arijit Ke, Xiangyu Gao, Yunjun Zhejiang Univ Hangzhou Zhejiang Peoples R China Aalborg Univ Aalborg Denmark Case Western Reserve Univ Cleveland OH 44106 USA

ISBN: (纸本)9798350384048;9798350384031

Generating explanations for graph neural networks (GNNs) is a crucial aspect to understand their decision-making processes, especially for complex analytical tasks such as graph classification [1]-[3]. Existing approaches [4]-[13] in this field are limited to providing explanations for individual instances or specific class labels. The main focus of these methods is on defining explanations as crucial input features, often in the shape of numerical encoding [14]. These methods often fall short in providing targeted and configurable explanations for multiple class labels of interest. Additionally, existing methods may return large or an excessive number of explanation structures, hence are not easily comprehensible. Moreover, these explanation structures often lack direct accessibility and cannot be queried easily, posing a challenge for expert users who seek to inspect the specific reasoning behind a GNN's decision based on domain knowledge. © 2024 IEEE.

关键词： approximation algorithm data mining deep learning explainable AI graph neural networks graph views

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：