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

Relay Node Placement in Wireless Sensor Networks With Respect to Delay and Reliability Requirements

IEEE SYSTEMS JOURNAL 2019年第3期13卷 2570-2581页

作者： Ma, Chaofan Liang, Wei Zheng, Meng Yang, Bo Zhongyuan Univ Technol Software Coll Zhengzhou 450007 Henan Peoples R China Chinese Acad Sci State Key Lab Robot Shenyang 110016 Liaoning Peoples R China Chinese Acad Sci Key Lab Networked Control Syst Shenyang 110016 Liaoning Peoples R China Chinese Acad Sci Inst Comp Technol Beijing 100190 Peoples R China

Wireless sensor networks are gradually employed in many applications that require reliable and real-time data transmission. As hop count is an important factor affecting end-to-end delay and reliability, we investigate the hop constrained relay node placement (HCRNP) problem in this paper. First, to achieve connectivity requirement, we study the connected HCRNP problem. Then, to design survivable network topologies against node failures, we study the 2-connected HCRNP problem. Correspondingly, two polynomial-time algorithms: cover-based 1-connected node placement (C1NP) and cover-based 2-connected node placement (C2NP) are proposed, respectively, to address the above two problems. Through rigorous analysis, we show that 1) C1NP has an approximation ratio better than existing algorithms for the connected HCRNP problem (i.e., O(1) for special settings and O(ln n) for arbitrary settings, where n is the number of SNs) and 2) C2NP is the first algorithm that can provide an explicit performance guarantee for the 2-connected HCRNP problem, i.e., whenever C2NP finds a feasible solution, the ratio of this solution to the optimal solution is guaranteed to be O(ln n). Finally, we verify the effectiveness of the proposed algorithms through extensive simulations.

关键词： approximation algorithm quality of service relay node placement (RNP) set cover wireless sensor networks (WSNs)

来源：评论

学校读者我要写书评

暂无评论

A Polynomial-time approximation Scheme for the MAXSPACE Advertisement Problem 10th

A Polynomial-time Approximation Scheme for the MAXSPACE Adve...

引用

10th Latin and American algorithms, Graphs, and Optimization Symposium (LAGOS)

作者： da Silva, Mauro R. C. Schouery, Rafael C. S. Pedrosa, Lehilton L. C. Univ Estadual Campinas Inst Comp Campinas SP Brazil

In the MAXSPACE problem, given a set of ads A, one wants to place a subset A' subset of A into K slots B-1, ..., B-K of size L. Each ad A(i) is an element of A has a size S-i and a frequency w(i). A schedule is feasible if the total size of ads in any slot is at most L, and each ad A(i) is an element of A' appears in exactly wi slots. The goal is to find a feasible schedule which maximizes the sum of the space occupied by all slots. We introduce a generalization, called MAXSPACE-RD, in which each ad A(i) also has a release date r(i) >= 1 and a deadline d(i) <= K, and may only appear in a slot B-j with r(i) <= j <= d(i). These parameters model situations where a subset of ads corresponds to a commercial campaign with an announcement date that may expire after some defined period. We present a polynomial-time approximation scheme for MAXSPACE-RD when K is bounded by a constant, i.e., for any epsilon > 0, we give a polynomial-time algorithm which returns a solution with value at least (1 - epsilon)Opt, where Opt is the optimal value. This is the best factor one can expect, since MAXSPACE is NP-hard, even if K = 2.

关键词： approximation algorithm PTAS Scheduling of Advertisements MAXSPACE

来源：评论

学校读者我要写书评

暂无评论

Online and offline algorithms for circuit switch scheduling

Online and offline algorithms for circuit switch scheduling

引用

作者： Yazdanbod, Sina Georgia Institute of Technology

学位级别：硕士

Motivated by the use of high-speed circuit switches in large scale data centers, we consider the problem of {\em circuit switch scheduling}. In this problem, we are given demands between pairs of servers and the goal is to schedule at every time step a matching between the servers while maximizing the total satisfied demand over time. The crux of this scheduling problem is that once one shift from one matching to a different one a fixed delay $\delta$ is incurred during which no data can be transmitted. For the offline version of the problem, we present an almost (1- 1/e) approximation ratio. Since the natural linear programming relaxation for the problem has an unbounded integrality gap, we adopt a hybrid approach that combines the combinatorial greedy with randomized rounding of a different suitable linear program. For the online version of the problem, we present a (bi-criteria) ((e-1)/(2e-1)-epsilon)-competitive ratio (for any constant epsilon >0 ) that exceeds time by an additive factor of O(delta/epsilon). We note that no uni-criteria online algorithm is possible. Surprisingly, we obtain the result by reducing the online version to the offline one.

关键词： approximation algorithm Online Matching Scheduling

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: approximation of Scheduling with Calibrations on Multiple Machines 31

Brief Announcement: Approximation of Scheduling with Calibra...

引用

31st ACM Symposium on Parallelism in algorithms and Architecturess (SPAA)

作者： Chen, Lin Li, Minming Lin, Guohui Wang, Kai Univ Houston Dept Comp Sci Houston TX 77204 USA City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Univ Alberta Dept Comp Sci Edmonton AB Canada HHL Leipzig Grad Sch Management Ctr Adv Studies Management Leipzig Saxony Germany

ISBN: (纸本)9781450361842

We study the scheduling problem with calibrations. In 2013, Bender et al. (SPAA '13) proposed a theoretical framework for the problem. Jobs of unit processing time with release times and deadlines are to be scheduled on parallel identical machines. The machines need to be calibrated to run jobs while a single calibration remains valid on a machine only for a time period of lengthT. The objective is to find a schedule that completes all jobs within their timing constraints and minimizes the total number of calibrations. In this paper, we aim to design an approximation algorithm to solve the problem. We propose a dynamic programming algorithm with polynomial running time when the number of machines is constant. In addition, we give a PTAS when the number of machines is input.

关键词： approximation algorithm Scheduling Calibration PTAS

来源：评论

学校读者我要写书评

暂无评论

Edit Distance with Multiple Block Operations

引用

COMPUTER JOURNAL 2019年第5期62卷 657-669页

作者： Gonen, Mira Shapira, Dana Storer, James A. Ariel Univ Dept Comp Sci IL-40700 Ariel Israel Brandeis Univ Dept Comp Sci Waltham MA 02454 USA

In this paper, we consider the edit distance with block moves, block copies and block deletions, which is shown to be NP-hard, and employ a simple left-to-right greedy sliding window algorithm that achieves a constant factor approximation ratio of 5. This is an improvement on the constant approximation of 12 presented by Ergun and Sahinalp (Ergun, F., Muthukrishnan, S., and Sahinalp, S. C. Comparing sequences with segment rearrangements. FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science), and is achieved by a proof that introduces two non-trivial kinds of substrings for different purposes, so recursive and non-recursive operations can be treated at the same time.

关键词： edit distance approximation algorithm constant factor approximation

来源：评论

学校读者我要写书评

暂无评论

Revenue Maximization and Learning in Products Ranking 21

Revenue Maximization and Learning in Products Ranking

引用

Proceedings of the 22nd ACM Conference on Economics and Computation

作者： Ningyuan Chen Anran Li Shuoguang Yang University of Toronto Toronto Canada London School of Economics and Political Science London United Kingdom The Hong Kong University of Science and Technology Hong Kong Hong Kong

ISBN: (纸本)9781450385541

Online retailing has seen steady growth over the last decade. According to the Digital Commerce (formerly Internet Retailer) analysis of the US Commerce Department's year-end retail data, online sales constituted 16% of all retail sales in 2019, and is forecast to reach higher levels in the next years due to the impact of COVID-19. For an online retailer, one of the most important decisions is the products' display positioning as it plays a crucial role in shaping customers' shopping behavior. Empirical evidence abounds. Baye et al. [2] find that a consumer's likelihood of purchasing from a firm is strongly related to the order in which the firm is listed on a webpage by a search engine. In the online advertising industry, it has been widely observed that ads placed higher on a webpage attract more clicks from consumers [1]. Given the importance of product ranking positions, the key question for online retailers is how to rank the products to maximize the *** question cannot be answered definitively, unless we can characterize and quantify how exactly customers react to products ranked in different positions. There are a number of reasons to explain the so-called position bias. The first reason is the limited attention of consumers. Eyetracking experiments show that the users are less likely to examine results near the bottom of the list. Besides limited attention, a customer seems to be more likely to buy a product ranked at the top, even though there is another similar product below inside her attention span. What explains this phenomenon at the individual level? Craswell et al. [3] provide a second explanation to the position bias using experiments, which is related to the satisficing behavior of customers. In particular, the customer views product sequentially and directly proceeds to purchasing a product once the utility of the product exceeds an acceptable threshold. The remaining products in the attention span are thus never viewed. Thus, positioning

关键词： online learning online products ranking revenue maximization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Corrigendum to “On the complexity of co-secure dominating set problem” [Inf. Process. Lett. 185 (2024) 106463]

引用

Information Processing Letters 2025年

作者： Bhawani Sankar Panda Soumyashree Rana Sounaka Mishra Dept. of Mathematics Indian Institute of Technology Delhi 110016 New Delhi India Department of Mathematics Indian Institute of Technology Madras India

We correct an error in Theorem 4 in our published paper Panda et al. [3] .

关键词： Domination Co-secure domination approximation algorithm Inapproximability APX-complete

来源：评论

学校读者我要写书评

暂无评论

Optimal backhauling for dense small-cell deployments using mmWave links

引用

COMPUTER COMMUNICATIONS 2019年 138卷 32-44页

作者： Huang, Po-Han Psounis, Konstantinos Univ Southern Calif Ming Hsieh Dept Elect Engn 3740 McClintock Ave Los Angeles CA 90089 USA

Dense small-cell deployments of 5G networks require a wireless backhaul to efficiently connect the small cells to the macro base station (BS). We envision a wireless backhaul architecture where cells are grouped into clusters. One small cell per cluster plays the role of "cluster head" connecting to the BS via a millimeter wave (mmWave) multiple-input and multiple-output (MIMO) link;the rest of the small cells in the cluster will then connect to the "cluster head" to reach the BS. We formulate the problem of jointly selecting the cluster heads and the number of BS antennas dedicated to each mmWave MIMO link between the BS and each cluster head to maximize system throughput as an integer linear program (ILP) and prove its NP-hardness. We then propose an O(ln vertical bar S vertical bar) approximation algorithm, where S is the number of small cells. We show via extensive simulations that the algorithm performs very close to the optimal in practice. Last, we show that the algorithm has, on average, more than 40% performance gain compared to previous work.

关键词： Wireless backhaul networks mmWave communication Hybrid beamforming Dense small-cell deployments approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating maximum uniquely restricted matchings in bipartite graphs

引用

DISCRETE APPLIED MATHEMATICS 2019年 267卷 30-40页

作者： Baste, Julien Rautenbach, Dieter Sau, Ignasi Univ Montpellier LIRMM Montpellier France Ulm Univ Inst Optimizat & Operat Res Ulm Germany Univ Montpellier LIRMM CNRS Montpellier France Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil

A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein (2001) and studied in a number of articles. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs, namely those excluding a C-4 or with maximum degree at most three. In particular, we achieve a ratio of 5/9 for subcubic bipartite graphs, improving over a 1/2-approximation algorithm proposed by Mishra (2011). (C) 2019 Elsevier B.V. All rights reserved.

关键词： Uniquely restricted matching Bipartite graph approximation algorithm Subcubic graph

来源：评论

学校读者我要写书评

暂无评论

Client assignment problems for latency minimization

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第3期37卷 889-900页

作者： Calinescu, Gruia Wang, Xiaolang IIT Dept Comp Sci Chicago IL 60616 USA

Interactivity is a primary performance measure for distributed interactive applications (DIAs). In a network supporting a DIA, interactivity performance depends on both client-to-server network latencies and inter-server network latencies. An optimization problem, which we term FCSA, is to find an optimum way how clients are assigned to servers such that the largest latency on an interactivity path between two clients (client 1 to server 1, server 1 to server 2, then server 2 to client 2) is minimized. Previous work showed that it is NP-hard to approximate this problem with a ratio better than 4/3 and gave a 3-approximation algorithm. In this paper, we give a (3/2)-approximation algorithm for FCSA, and show that it is NP-hard to obtain a better ratio. We also give a (3/2)-approximation algorithm when server capacity constraints are considered.

关键词： approximation algorithm Bottleneck minimization problem Best possible approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：