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

Partitioning Into Prescribed Number of Cycles and Mod k T -join With Slack

Procedia Computer Science 2021年 195卷 12-20页

作者： Jordan Barrett Salomon Bendayan Yanjia Li Bruce Reed Department of Mathematics McGill University Montreal Canada Department of Combinatorics & Optimization University of Waterloo Waterloo Canada Department of Computer Science McGill University Montreal Canada

The input to a PPNC instance is integers n and p , and a non-negative real weighting of the edges of the clique K n on the vertex set {1,..., n } . We are asked to find a set of p disjoint cycles spanning {1,..., n } and subject to this such that the sum of the weights of the edges is minimized. We provide an efficient approximation algorithm for the metric version of this problem which has an approximation ratio of 4 if p ≤ n/5 and an approximation ratio of 51 for larger p . For p > n/5, our algorithm uses a subroutine which approximately solves the Mod 3 T -join With Slack problem. The input to an instance of Mod k T -join with Slack consists of integers n and B , a non-negative weighting of the edges of the clique K n , and a label l(v) from {0,1,..., k - 1} on each vertex of K n . We are asked to find the minimum weight spanning forest F from amongst those satisfying ∑ T∈F ((∑ v∈V(T) l(v)) mod k ) ≤ B . If k = 2 and B = 0 this is the well-studied T -join problem which can be solved exactly in polynomial time.

关键词： Hamiltonian p-median problem T -join approximation algorithm Graph partition

来源：评论

学校读者我要写书评

暂无评论

On the Maximum Edge-Pair Embedding Bipartite Matching 14th

On the Maximum Edge-Pair Embedding Bipartite Matching

引用

14th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Cam Ly Nguyen Suppakitpaisarn, Vorapong Surarerks, Athasit Vajanopath, Phanu Toshiba Co Ltd Kawasaki Kanagawa Japan Univ Tokyo Tokyo Japan Chulalongkorn Univ Bangkok Thailand

ISBN: (纸本)9783030398811;9783030398804

Given a set of edge pairs in a bipartite graph, we want to find a bipartite matching that includes a maximum number of those edge pairs. While the problem has many applications to wireless localization, to the best of our knowledge, there is no theoretical work for the problem. In this work, unless P = NP, we show that there is no constant approximation for the problem. Suppose that k denotes the maximum number of input edge pairs such that a particular node can be in. Inspired by experimental results, we consider the case that k is small. While there is a simple polynomial-time algorithm for the problem when k is one, we show that the problem is NP-hard when k is greater than one. We also devise an efficient O(k)-approximation algorithm for the problem.

关键词： Wireless localization Computational complexity approximation algorithm Network optimization

来源：评论

学校读者我要写书评

暂无评论

A Structured Approach to Modifying Successful Heuristics 12th

A Structured Approach to Modifying Successful Heuristics

引用

12th International Joint Conference on Computational Intelligence (IJCCI) / 12th International Conference on Evolutionary Computation Theory and Applications (ECTA)

作者： Martin, Simon P. Craven, Matthew J. Woodward, John R. Univ Plymouth Ctr Math Sci Plymouth PL4 8AA Devon England Queen Mary Univ London Comp Sci Mile End Rd London E1 4FZ England

ISBN: (纸本)9789897584756

In some cases, heuristics may be transferred easily between different optimisation problems. This is the case if these problems are equivalent or dual (e.g., maximum clique and maximum independent set) or have similar objective functions. However, the link between problems can further be defined by the constraints that define them. This refining can be achieved by organising constraints into families and translating between them using gadgets. If two problems are in the same constraint family, the gadgets tell us how to map from one problem to another and which constraints are modified. This helps better understand a problem through its constraints and how best to use domain specific heuristics. In this position paper, we argue that this allows us to understand how to map between heuristics developed for one problem to heuristics for another problem, giving an example of how this might be achieved.

关键词： Heuristic Gadget approximation algorithm Optimisation Problem

来源：评论

学校读者我要写书评

暂无评论

A Graph-Based Approach for Active Learning in Regression

A Graph-Based Approach for Active Learning in Regression

引用

SIAM International Conference on Data Mining (SDM)

作者： Zhang, Hongjing Ravit, S. S. Davidson, Ian Univ Calif Davis Dept Comp Sci Davis CA 95616 USA Univ Virginia Biocomplex Inst & Initiat Charlottesville VA 22903 USA SUNY Albany Albany NY 12222 USA

ISBN: (纸本)9781611976236

Active learning aims to reduce labeling efforts by selectively asking humans to annotate the most important data points from an unlabeled pool and is an example of human-machine interaction. Though active learning has been extensively researched for classification and ranking problems, it is relatively understudied for regression problems. Most existing active learning for regression methods use the regression function learned at each active learning iteration to select the next informative point to query. This introduces several challenges such as handling noisy labels, parameter uncertainty and overcoming initially biased training data. Instead, we propose a feature-focused approach that formulates both sequential and batch-mode active regression as a novel bipartite graph optimization problem. We conduct experiments on both noise-free and noisy settings. Our experimental results on benchmark data sets demonstrate the effectiveness of our proposed approach.

关键词： Active learning bipartite graphs regression approximation algorithm noisy data

来源：评论

学校读者我要写书评

暂无评论

Acyclic Matching in Some Subclasses of Graphs 31st

Acyclic Matching in Some Subclasses of Graphs

引用

31st International Workshop on Combinatorial algorithms (IWOCA)

作者： Panda, B. S. Chaudhary, Juhi Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

ISBN: (纸本)9783030489656;9783030489663

A subset M subset of E of edges of a graph G = (V, E) is called a matching if no two edges of M share a common vertex. A matching M in a graph G is called an acyclic matching if G[V (M)], the subgraph of G induced by the M-saturated vertices of G is acyclic. The ACYCLIC MATCHING PROBLEM is the problem of finding an acyclic matching of maximum size. The decision version of the ACYCLIC MATCHING PROBLEM is known to be NP-complete for general graphs as well as for bipartite graphs. In this paper, we strengthen this result by showing that the decision version of the ACYCLIC MATCHING PROBLEM remains NP-complete for comb-convex bipartite graphs and dually-chordal graphs. On the positive side, we present linear time algorithms to compute an acyclic matching of maximum size in split graphs and proper interval graphs. Finally, we show that the ACYCLIC MATCHING PROBLEM is hard to approximate within a factor of n(1-epsilon) for any epsilon > 0, unless P = NP and the ACYCLIC MATCHING PROBLEM is APX-complete for 2k + 1-regular graphs for k >= 3, where k is a constant.

关键词： Matching Bipartite graphs Chordal graphs Graph algorithm NP-completeness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Linear programming based approximation for unweighted induced matchings-Breaking the Δ barrier

引用

DISCRETE OPTIMIZATION 2020年 38卷 100593-100593页

作者： Baste, Julien Fuerst, Maximilian Rautenbach, Dieter Ulm Univ Inst Optimizat & Operat Res Ulm Germany

A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (2018) provide an approximation algorithm with ratio Delta for the weighted version of the induced matching problem on graphs of maximum degree Delta. Their approach is based on an integer linear programming formulation whose integrality gap is at least Delta - 1, that is, their approach offers only little room for improvement in the weighted case. For the unweighted case though, we conjecture that the integrality gap is at most 5/8 Delta + O(1), and that also the approximation ratio can be improved at least to this value. We provide primal-dual approximation algorithms with ratios (1 - epsilon)Delta + 1/2 for general Delta with epsilon approximate to 0.02005, and 7/3 for Delta = 3. Furthermore, we prove a best-possible bound on the fractional induced matching number in terms of the order and the maximum degree. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Induced matching Strong matching approximation algorithm Linear programming Primal-dual approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Novel Initialization algorithm for Fuzzy C-means Problem 1

引用

16th International Conference on Theory and Applications of Models of Computation (TAMC)

作者： Liu, Qian Liu, Jianxin Li, Min Zhou, Yang Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

ISBN: (数字)9783030592677

ISBN: (纸本)9783030592660;9783030592677

The fuzzy C-means problem belongs to soft clustering problem, where each given point has relationship to every center point. This problem is different from the k-means problem, where each point should belong to only one cluster. In this paper, we design one seeding algorithm for fuzzy C-means problem and obtain performance ratio O(klnk). We also give the performance guarantee O(k(2)lnk) of the seeding algorithm based on k-means++ for fuzzy C-means problem. At last, we present our numerical experiment to show the validity of the algorithms.

关键词： Fuzzy C-means problem approximation algorithm Seeding algorithm

来源：评论

学校读者我要写书评

暂无评论

Area Charging for Wireless Rechargeable Sensors 29

Area Charging for Wireless Rechargeable Sensors

引用

29th International Conference on Computer Communications and Networks (ICCCN)

作者： Dai, Haipeng Wang, Xiaoyu Xu, Lijie Dong, Chao Liu, Qian Meng, Lei Chen, Guihai Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China Nanjing Univ Posts & Telecommun Jiangsu Key Lab Big Data Secur & Intelligent Proc Nanjing Jiangsu Peoples R China Nanjing Univ Aeronaut & Astronaut Nanjing Jiangsu Peoples R China

ISBN: (纸本)9781728166070

In this paper, we consider the problem of area charging, that is, assuming that there is a mobile charger (MC) equipped with a directional wireless charger whose charging area is in the shape of a sector, and the MC can only recharge sensors on the boundary of an Area of Interest (AOI), how to design an efficient charging scheme for the MC to recharge any sensor inside the AOI with efficient energy while its overall charging time is minimized. To address this problem, we first partition the AOI into two types of subareas, i.e., rectangle-like subareas and sector-like subareas, based on the Medial Axis of the AOI. Second, we propose rectangle-based moving strategy for the rectangle-like subareas, and sector-based rotating strategy for the sector-like subareas, respectively, for the MC. Finally, we calculate charging time of all subareas based on the above two moving strategies, and prove that our algorithm achieves a constant approximation ratio. We evaluate our algorithm by conducting extensive simulation. The results show that on average, other comparison algorithms require at least 18:70 times of charging time of that of our algorithm.

关键词： Mobile charging wireless rechargeable sensors approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent 2020

Positive Semidefinite Programming: Mixed, Parallel, and Widt...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Jambulapati, Arun Lee, Yin Tat Li, Jerry Padmanabhan, Swati Tian, Kevin Stanford Univ Stanford CA 94305 USA Univ Washington Seattle WA 98195 USA Microsoft Res Seattle WA USA Microsoft Res Redmond WA USA

ISBN: (纸本)9781450369794

We study mixed packing and covering semidefinite programs (SDPs) and give the first approximation algorithm with polylogarithmic dependence on width. Mixed packing and covering SDPs constitute a fundamental algorithmic primitive with applications in combinatorial optimization, robust learning, and quantum complexity. The current approximate solvers for positive semidefinite programming can handle only pure packing instances, and technical hurdles prevent their generalization to a wider class of positive instances. For a given multiplicative accuracy of c, our algorithm takes O (log(3)(ndp) . epsilon(-3)) parallelizable iterations, where n, d are the problem dimensions and rho is a width parameter of the instance, generalizing or improving all previous parallel algorithms in the positive linear and semidefinite programming literature. When specialized to pure packing SDPs, our algorithm's iteration complexity is O (log(2) (nd) . epsilon(-2)), a slight improvement and derandomization of the state-of-the-art [AI,016, rrl16, WNIMI-215]. For several common structured instances, the iterations of our algorithm run in nearly-linear time. In doing so, we give matrix analytic techniques to overcome obstacles that have stymied prior approaches to this problem, as stated in [PTZ16, NIRWZ16]. Crucial to our analysis are a simplification of existing algorithms for mixed positive linear programs, achieved by removing an asymmetry from modifying covering constraints, and a suite of matrix inequalities with proofs based on analyzing the Schur complements of matrices in a higher dimension. We hope that our algorithm and techniques open the door to improved solvers for positive semidefinite programming and its applications.

关键词： semidefinite programming mixed packing and covering approximation algorithm parallel algorithm width-independent algorithm

来源：评论

学校读者我要写书评

暂无评论

Affinitive Diversity-Aware Task Allocation in Spatial Crowdsourcing 13

Affinitive Diversity-Aware Task Allocation in Spatial Crowds...

引用

13th IEEE International Conference on Services Computing (SCC) / 13th IEEE International Conference on Web Services (ICWS)

作者： Bhatti, Shahzad Sarwar Chang, Yiding Gao, Xiaofeng Chen, Guihai Shanghai Jiao Tong Univ Shanghai Key Lab Data Sci Dept Comp Sci & Engn Shanghai Peoples R China

ISBN: (纸本)9781728187860

With the rapid development of mobile network and devices, spatial crowdsourcing (SC) has recently attracted much attention. For the improvement of quality of service (QoS) in spatial crowdsourcing platforms, existing works usually adopt the many-to-one strategy - assigning multiple workers as a team for each published task. However, such an allocation scheme fails to consider team characteristics which can strongly affect the QoS for some experience-sensitive collaborative tasks. In this paper, we jointly consider two team characteristics to further improve the QoS: Diversity, which is the union of experiences within a team and Affinity, which is how efficiently team members collaborate. Inspired by these two characteristics, we study an important problem, namely, Affinitive Diversity-Aware Spatial Crowdsourcing (ADA-SC), which aims to find an allocation scheme, such that each team satisfies the affinity requirement of the corresponding task and maximizes the team diversity under budget and spatial constraints. Since ADA-SC is proven to be NP-hard by reduction from the set cover problem with non-linear constraints, we propose two submodular approximation algorithms with pruning strategies for two single-task scenarios. Then a greedy-based algorithm is designed for the multi-task scenario. Extensive experiments on real and synthetic data verify the effectiveness of our proposed methods.

关键词： crowdsourcing social network approximation algorithm quality of service combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：