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

An Improved approximation algorithm for the Shortest Link Scheduling Problem in Wireless Networks under SINR and Hypergraph Models 9

引用

9th International Conference on Wireless algorithms, Systems, and Applications (WASA)

作者： Wang, Cui Yu, Jiguo Yu, Dongxiao Huang, Baogui Qufu Normal Univ Sch Comp Sci Ri Zhao 276826 Shandong Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9783319077826;9783319077819

Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling(SLS) under SINR and hypergraph models, and propose an approximation algorithm GeoSLS by using geometric links for better performance than GOW* proposed by Blough, Resta and Santi(2010). For the average length of scheduling, GeoSLS decreases 1/m compared with GOW*, where m = left perpendicular4p+(Delta(max)-4).(1-p)right perpendicular is the expected number of the links in the set V returned by HyperMaxLS and 0 < p < 1 is the probability of the number of the links scheduled simultaneously in the set V. In the worst, ideal and average cases, the ratios of time complexity of our algorithm GeoSLS to GOW* are O(Delta(max)/(k) over bar), O(1/((k) over ***(max))) and O(Delta(max)/((k) over bar .m)), respectively, where 1 < <(k)over bar> < Delta(max) is a constant called the SNR diversity of instance G.

关键词： Wireless Networks Shortest Link Scheduling approximation algorithm Hypergraph Model SINR

来源：评论

学校读者我要写书评

暂无评论

Near-Linear Time Constant-Factor approximation algorithm for Branch-Decomposition of Planar Graphs 40

引用

40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Gu, Qian-Ping Xu, Gengchun Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

ISBN: (纸本)9783319123400;9783319123394

We give constant-factor approximation algorithms for branch-decomposition of planar graphs. Our main result is an algorithm which for an input planar graph G of n vertices and integer k, in O(n log(4) n) time either constructs a branch-decomposition of G with width at most (2 + delta)k, delta > 0 is a constant, or a (k + 1) x [k+1/2] cylinder minor of G implying O(G) > k, bw(G) is the branchwidth of G. This is the first (n) time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous min{0(n(1+epsilon)), O(nk(3))} (epsilon > 0 is a constant) time constant-factor approximations. For a planar graph G and k = bw(G), a branch-decomposition of width at most (2+delta)k and gxg/2 cylinder/grid minor with g = k/beta, beta> 2 is constant, can be computed by our algorithm in 0(n log(4) n log k) time.

关键词： Branch-/tree-decompositions Grid minor Planar graphs approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Support group formation for users with depression in social networks

引用

EXPERT SYSTEMS WITH APPLICATIONS 2025年 276卷

作者： Yang, Xingwei Li, Guang Noorian, Zeinab Toronto Metropolitan Univ 55 Dundas St W Toronto ON M5G 2C3 Canada Queens Univ 143 Union St Kingston ON K7L 3N6 Canada

There is a growing interest in using social media for online interventions via peer support groups to address mental health challenges. However, existing groups are often self-formed or initiated by healthcare professionals. To the best of our knowledge, there has been limited work within the health domain, specifically focusing on establishing communities or groups providing focused support to individuals facing health challenges. Our study addresses these gaps by introducing a new method for creating support groups on social networks for individuals with mental illness. We aim to identify dense sub-graphs where members share interests with the target users and are in close proximity to them. We demonstrate that finding an optimal support group for users with mental illness is NP-hard. To address this, we propose a 2-approximation algorithm with a runtime of O(n2s). This suggests that our algorithm finds closely connected support group members around users with depression, demonstrating theoretical compactness and relative effectiveness. Using real-world Social Media MyPersonality Dataset, we validate our approach and show that our algorithm efficiently finds groups with shared interests and small proximity across various group sizes. Even for a group size of 10, our algorithm runs in less than 13 ms. Compared to an exhaustive search, our algorithm produces support groups with only a 12%-15% larger diameter. This approach can potentially facilitate more effective intervention and treatment by connecting users with similar struggles, reducing social isolation, and aiding recovery.

关键词： Social support group Depression intervention Social media computing approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The algorithm and complexity of co-secure domination in geometric intersection graphs

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2025年第1期44卷 1-14页

作者： Wang, Cai-Xia Yang, Yu Xu, Shou-Jun Lanzhou Univ Gansu Ctr Appl Math Sch Math & Stat Lanzhou 730000 Gansu Peoples R China

Given a graph G with vertex set V, a dominating set S subset of V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S\subseteq V$$\end{document} is a co-secure dominating set of G if for every vertex u is an element of S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u\in S$$\end{document}, there is a vertex v is an element of V\S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v\in V{\setminus } S$$\end{document} adjacent to u such that (S\{u})boolean OR{v}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(S{\setminus }\{u\})\cup \{v\}$$\end{document} is a dominating set of G. The minimum co-secure dominating set (or, for short, MCSDS) problem asks to find an MCSDS in a given graph. In this paper, first we show that the decision version of the problem is NP-complete in grid graphs and supergrid graphs. Consequently, we show that the problem remains NP-complete for unit disk and unit square graphs. Secondly, we show that the MCSDS problem is APX-hard in d-box graphs for any fixed integer d >= 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d\ge 2$$\end{document}. Finally, we giv

关键词： Co-secure domination Geometric intersection graphs NP-complete APX-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An Echo Pressure Model Based on Mutil-Gaussian Beam Theory for Measuring the Liquid Level in Special Field

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2025年第2期37卷

作者： Zhang, Bin Wei, Yuejuan Zhang, Shuqui Li, Qing Qiang, Yan North Univ China Software Sch Taiyuan Peoples R China

In aviation, petroleum and chemical industries and other special areas of production, since the liquid in containers mostly are flammable, explosive, volatile, and corrosive mixtures, the accurate measurement of the liquid level is essential to the real-time control and production process. In this study, an approximation algorithm based on echo pressure model for measuring the liquid level in special field is proposed in this paper. According to the model, a complete lateral incident ultrasonic measurement system is constructed for the inductive liquid level detection technology in special applications, an algorithm model of the echo pressure is established, which provides the determination of the liquid level relying on the characteristic curve of the echo pressure. The model in this study converts complex interaction problems of sound fields into the echo pressure calculation, which quickly determines performance parameters of sound fields, and a virtual reflection method is used to calculate the sound pressure of the receiving transducer in different states, which reduces computational complexity, finally, through the simulation and experiment, the algorithm is validated. The results are consistent with expectations, and the algorithm can be further applied in practice.

关键词： approximation algorithm echo pressure lateral incident

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Median Hub Location Problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第2期38卷 375-401页

作者： Benedito, Marcelo P. L. Pedrosa, Lehilton L. C. Univ Estadual Campinas Inst Comp Campinas SP Brazil

In Hub Location Problems, an input is composed of sets of clients, locations and a pairs of clients;a solution is a subset of locations to open hubs and an assignment for each pair of clients to a route starting in the first client, passing through one or more hubs and ending in the second client. The objective is to find a solution that minimizes the length of all routes plus the cost of opening hubs. The currently known approximation algorithms consider only the case in which the set of hubs is given as part of the input and the problem is assigning clients to hubs. For a metric space setting, this work presents the first constant-factor approximation algorithms for the problem of, simultaneously, selecting hubs and allocating clients. A few variants are considered, depending on whether the number of open hubs is given in the input or a client must be assigned to a single hub. In particular, we give an LP-rounding 2.48-approximation algorithm for the Single-Allocation Median Hub Location Problem, using a new formulation and exploiting its symmetries.

关键词： approximation algorithm Hub Location Problem LP-rounding

来源：评论

学校读者我要写书评

暂无评论

approximation Designs for Energy Harvesting Relay Deployment in Wireless Sensor Networks

引用

Journal of Computer Science & Technology 2022年第4期37卷 779-796页

作者： Yi Wang Yi-Xue Liu Shun-Jia Zhu Xiao-Feng Gao Chen Tian School of Modern Posts Nanjing University of Posts and TelecommunicationsNanjing 210003China State Key Laboratory for Novel Software Technology Nanjing UniversityNanjing 210023China ByteDance Inc. Shanghai 201100China Key Laboratory of Artificial Intelligence of Ministry of Education Department of Computer Science and EngineeringShanghai Jiao Tong UniversityShanghai 200240China

Energy harvesting technologies allow wireless devices to be recharged by the surrounding environment, providing wireless sensor networks (WSNs) with higher performance and longer lifetime. However, directly building a wireless sensor network with energy harvesting nodes is very costly. A compromise is upgrading existing networks with energy harvesting technologies. In this paper, we focus on prolonging the lifetime of WSNs with the help of energy harvesting relays (EHRs). EHRs are responsible for forwarding data for sensor nodes, allowing them to become terminals and thus extending their lifetime. We aim to deploy a minimum number of relays covering the whole network. As EHRs have several special properties such as the energy harvesting and depletion rate, it brings great research challenges to seek an optimal deployment strategy. To this end, we propose an approximation algorithm named Effective Relay Deployment algorithm, which can be divided into two phases: disk covering and connector insertion using the partitioning technique and the Steinerization technique, respectively. Based on probabilistic analysis, we further optimize the performance ratio of our algorithm to (5 + 6/K) where K is an integer denoting the side length of a cell after partitioning. Our extensive simulation results show that our algorithm can reduce the number of EHRs to be deployed by up to 45% compared with previous work and thus validate the efficiency and effectiveness of our solution.

关键词： approximation algorithm constraint relay deployment energy harvesting wireless sensor network

来源：评论

学校读者我要写书评

暂无评论

A discrete dwarf mongoose optimization algorithm to solve task assignment problems on smart farms

引用

CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS 2024年第5期27卷 6185-6204页

作者： Xu, Minzhi Li, Weidong Zhang, Xuejie Su, Qian Yunnan Univ Sch Informat Sci & Engn Kunming Yunnan Peoples R China Yunnan Univ Sch Math & Stat Kunming Yunnan Peoples R China

In this study, we propose a novel cloud-edge collaborative task assignment model for smart farms that consists of a cloud server, m edge servers, and n sensors. The edge servers rely solely on solar-generated energy, which is limited, whereas the cloud server has access to a limitless amount of energy supplied by the smart grid. Each entire task from a sensor is processed by either an edge server or the cloud server. We consider the task to be unsplittable. Building on the algorithm for the multimachine job scheduling problem, we develop a corresponding approximation algorithm. In addition, we propose a new discrete heuristic based on the dwarf mongoose optimization algorithmm, named the discrete dwarf mongoose optimization algorithm, and we utilize the proposed approximation algorithm to improve the convergence speed of this heuristic while yielding better solutions. In this study, we consider task sets with heavy tasks independently, where a heavy task is a task that requires many computing resources to process. If such tasks are assigned as ordinary tasks, the assignment results may be poor. Therefore, we propose a new method to solve this kind of problem.

关键词： Cloud-edge collaborative Unsplittable approximation algorithm Dwarf mongoose algorithm Heavy tasks

来源：评论

学校读者我要写书评

暂无评论

Optimizing Resource Allocation for Wireless VR Services

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2024年第5期17卷 2719-2732页

作者： Wang, Chih-Hang Shi, Yishuo Yang, De-Nian Chen, Chih-Yen Liao, Wanjiun Acad Sinica Inst Informat Sci Taipei City 115201 Taiwan Wenzhou Univ Coll Math & Phys Dept Stat & Informat Sci Wenzhou 325035 Peoples R China Acad Sinica Res Ctr Informat Technol Innovat Taipei 115201 Taiwan Natl Taiwan Univ Dept Elect Engn Taipei 10617 Taiwan

The virtual reality (VR) market is expected to reach 202.7 billion dollars by 2028, at a compound annual growth rate of 24.74% over the forecast period 2023-2028. It motivates innovative VR services in touring, E-commerce, and social activities, and effective VR video streaming becomes essential. However, VR services are envisaged to consume a large amount of bandwidth, but current research primarily focuses on multimedia streaming for each individual user without considering the opportunity of view synthesis for multicast to reduce wireless resource consumption further. In this article, we formulate a new optimization problem VR Content Sharing and Multicasting (VCSM) and prove the NP-hardness. Then, we propose an approximation algorithm, named Efficient View Synthesis and Multicasting (EVSM), to select multicast views and their Modulation and Coding Schemes (MCS) for wireless VR services. Afterward, we extend EVSM to support dynamic user behaviors and increase scalability with distributed mobile edge computing. We also explore the intrinsic properties of view selections to find the optimal solution for regular user deployment. Experiment results show that EVSM can effectively reduce bandwidth consumption for VR services by more than 50%.

关键词： Bandwidth Multicast algorithms Wireless communication Multicast communication Heuristic algorithms approximation algorithms Streaming media Optimization approximation algorithm multicast VR

来源：评论

学校读者我要写书评

暂无评论

Multiple identical serial-batch machines scheduling with release dates and submodular rejection penalties

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第2期49卷 1-27页

作者： Geng, Zhichao Lu, Lingfa Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Peoples R China

In this paper we study a scheduling problem with release dates and submodular rejection penalties on multiple (parallel) identical serial-batch machines. For this problem, each machine processes jobs in batches, jobs in a common batch start and finish simultaneously, and the duration of a batch is equal to the sum of a setup time and the total processing time of jobs in it. Some jobs are accepted and processed on the machines, while the left jobs are rejected with penalty and the total rejection penalty is determined by a submodular function. The objective function to be minimized is the sum of the makespan of accepted jobs and the total rejection penalty. For the scenario of an arbitrary number of machines and submodular rejection penalties, we give a 2-approximation algorithm by which the objective function value of the obtained schedule is no more than twice that of the optimal schedule. For the scenario of a fixed number of machines and linear rejection penalties, we give a pseudo-polynomial-time dynamic programming exact algorithm and a fully polynomial-time approximation scheme.

关键词： Scheduling Serial-batch Submodular function approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：