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

13th Innovations in Theoretical Computer Science Conference, ITCS 2022

作者： Wang, Weina Gupta, Anupam Williams, Jalani K. Computer Science Department Carnegie Mellon University PittsburghPA United States

ISBN: (纸本)9783959772174

We develop approximation algorithms for set-selection problems with deterministic constraints, but random objective values, i.e., stochastic probing problems. When the goal is to maximize the objective, approximation algorithms for probing problems are well-studied. On the other hand, few techniques are known for minimizing the objective, especially in the adaptive setting, where information about the random objective is revealed during the set-selection process and allowed to influence it. For minimization problems in particular, incorporating adaptivity can have a considerable effect on performance. In this work, we seek approximation algorithms that compare well to the optimal adaptive policy. We develop new techniques for adaptive minimization, applying them to a few problems of interest. The core technique we develop here is an approximate reduction from an adaptive expectation minimization problem to a set of adaptive probability minimization problems which we call threshold problems. By providing near-optimal solutions to these threshold problems, we obtain bicriteria adaptive policies. We apply this method to obtain an adaptive approximation algorithm for the Min-Element problem, where the goal is to adaptively pick random variables to minimize the expected minimum value seen among them, subject to a knapsack constraint. This partially resolves an open problem raised in [5]. We further consider three extensions on the Min-Element problem, where our objective is the sum of the smallest k element-weights, or the weight of the min-weight basis of a given matroid, or where the constraint is not given by a knapsack but by a matroid constraint. For all three of the variations we explore, we develop adaptive approximation algorithms for their corresponding threshold problems, and prove their near-optimality via coupling arguments. © Weina Wang, Anupam Gupta, and Jalani K. Williams;licensed under Creative Commons License CC-BY 4.0

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

t-path Based Reliable and Real-time Routing in Battery-Free Wireless Sensor Network 23

t-path Based Reliable and Real-time Routing in Battery-Free ...

引用

23rd IEEE International Conference on High Performance Computing and Communications, 7th IEEE International Conference on Data Science and Systems, 19th IEEE International Conference on Smart City and 7th IEEE International Conference on Dependability in Sensor, Cloud and Big Data Systems and Applications, HPCC-DSS-SmartCity-DependSys 2021

作者： Chen, Kunyi Gao, Hong Cheng, Siyao Chen, Quan Li, Jianzhong Harbin Institute of Technology China Guangdong University of Technology China

ISBN: (纸本)9781665494571

Wireless Sensor Networks are deployed to sense data from the physical world and transmit these data to the server(s). To reduce the maintenance cost of replacing batteries, Energy-Harvesting nodes are developed which can get recharged from Solar Power, Radio Frequency, and other environmental energy resources. We term the network consist of energy-harvesting nodes as Battery-Free WSNs (BF-WSNs). Environmental energy is inherently time-varying and exhibits a high degree of heterogeneity. These features bring challenges to routing design. In this paper, we focus on the reliability and real-time issues and propose an opportunistic strategy as time synchronization is hard and expensive to reach in BF-WSN. We first model BF-WSNs as a directed weighted multigraph and propose a novel definition called t-path to describe the time-varying availability feature of BF-nodes. Further, we show that the problem is NP-Hard. We present a centralized approximate algorithm and prove that the ratio bound is 2 under two conditions. This paper also presents a distributed algorithm. Comprehensive simulations have been performed to evaluate the performance of the proposed algorithms and the results show that the efficiency of our algorithms. © 2021 IEEE.

关键词： Wireless sensor networks Simulation Reliability theory approximation algorithms Routing Reliability engineering Real-time systems

来源：评论

学校读者我要写书评

暂无评论

Study on Degree of Influence of P-Delta Effects on Strength of Jack-Up Leg Structures in Vietnamese Conditions 2nd

Study on Degree of Influence of P-Delta Effects on Strength ...

引用

2nd Vietnam Symposium on Advances in Offshore Engineering, VSOE 2021

作者： Hau, Pham Hien Chinh, Vu Dan Tuan, Dang Dinh National University of Civil Engineering Hanoi Viet Nam

ISBN: (纸本)9789811677342

Jack-up is a type of offshore platforms using for oil & gas exploitation in Vietnam. In operating conditions, jack-up hull structures with large weight are lifted to high elevation and supported by slender leg structures. When subjected to environmental loading, they have large lateral displacements. In these cases, P-Delta effects are usually considered. In current standards, the effects are simulated by approximate formulas. In the previous paper, we studied on evaluating P-Delta effects on the durability of jack-up structures in static analyses according to large deformation theory and approximate methods of ABS and DnV standards. The research clarified the different influences of the models. However, in operating conditions, the hull weights and hull levels of jack-up platforms may be changed. It leads to the variability of P-Delta effects. In this paper, we propose to assess the degree of influence of P-Delta effects to strength of jack-up leg structures in Vietnamese conditions. The problem is studied by analyses of a simple model and FEM models. For the simple model, we will estimate the preliminary changing of P-Delta effects by an equivalent structural model. Then we establish global models in some operating status using SACS program to analyze jack-up leg structures in relation with different methods for consideration of P-Delta effects. The strength analysis results will be presented to evaluate real influences of the effects on jack-up structures. The research results will give useful recommendations for consultancy companies to analyze and assess jack-up platforms operating in Viet Nam offshore areas. © 2022, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Complexity and algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond 33

Complexity and Algorithms for ISOMETRIC PATH COVER on Chorda...

引用

33rd International Symposium on algorithms and Computation, ISAAC 2022

作者： Chakraborty, Dibyayan Dailly, Antoine Das, Sandip Foucaud, Florent Gahlawat, Harmender Ghosh, Subir Kumar Univ Lyon CNRS ENS de Lyon Université Claude Bernard Lyon 1 LIP UMR5668 France G-SCOP Univ. Grenoble-Alpes Grenoble France Indian Statistical Institute Kolkata India Université Clermont-Auvergne CNRS Mines de Saint-Étienne Clermont-Auvergne-INP LIMOS Clermont-Ferrand63000 France Univ. Orléans INSA Centre Val de Loire LIFO EA 4022 OrléansCedex 2 F-45067 France Ben-Gurion University of the Negev Beer-Sheva Israel Ramakrishna Mission Vivekananda Educational and Research Institute Kolkata India

ISBN: (纸本)9783959772587

A path is isometric if it is a shortest path between its endpoints. In this article, we consider the graph covering problem Isometric Path Cover, where we want to cover all the vertices of the graph using a minimum-size set of isometric paths. Although this problem has been considered from a structural point of view (in particular, regarding applications to pursuit-evasion games), it is little studied from the algorithmic perspective. We consider Isometric Path Cover on chordal graphs, and show that the problem is NP-hard for this class. On the positive side, for chordal graphs, we design a 4-approximation algorithm and an FPT algorithm for the parameter solution size. The approximation algorithm is based on a reduction to the classic path covering problem on a suitable directed acyclic graph obtained from a breadth first search traversal of the graph. The approximation ratio of our algorithm is 3 for interval graphs and 2 for proper interval graphs. Moreover, we extend the analysis of our approximation algorithm to k-chordal graphs (graphs whose induced cycles have length at most k) by showing that it has an approximation ratio of k + 7 for such graphs, and to graphs of treelength at most , where the approximation ratio is at most 6 + 2. © Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, and Subir Kumar Ghosh.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On Streaming algorithms for Geometric Independent Set and Clique 1

引用

20th International Workshop on approximation and Online algorithms, WAOA 2022

作者： Bhore, Sujoy Klute, Fabian Oostveen, Jelle J. Indian Institute of Science Education and Research Bhopal India Utrecht University Utrecht Netherlands

ISBN: (数字)9783031183676

ISBN: (纸本)9783031183669

We study the maximum geometric independent set and clique problems in the streaming model. Given a collection of geometric objects arriving in an insertion only stream, the aim is to find a subset such that all objects in the subset are pairwise disjoint or intersect respectively. We show that no constant factor approximation algorithm exists to find a maximum set of independent segments or 2-intervals without using a linear number of bits. Interestingly, our proof only requires a set of segments whose intersection graph is also an interval graph. This reveals an interesting discrepancy between segments and intervals as there does exist a 2-approximation for finding an independent set of intervals that uses only O(α(I) log | I| ) bits of memory for a set of intervals I with α(I) being the size of the largest independent set of I. On the flipside we show that for the geometric clique problem there is no constant-factor approximation algorithm using less than a linear number of bits even for unit intervals. On the positive side we show that the maximum geometric independent set in a set of axis-aligned unit-height rectangles can be 4-approximated using only O(α(R) log | R| ) bits. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Comments on "Precoding and Artificial Noise Design for Cognitive MIMOME Wiretap Channels"

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2021年第3期70卷 2917-2921页

作者： Khojastehnia, Mahdi Loyka, Sergey Univ Ottawa Sch Elect Engn & Comp Sci Ottawa ON K1N 6N5 Canada

Several gaps and errors in "Precoding and Artificial Noise Design for Cognitive MIMOME Wiretap Channels" by Fang et al. are identified and corrected. While accommodating these corrections, a rigours proof is given that the successive convex approximation algorithm of Fang et al. for secrecy rate maximization (SRM) does generate an increasing and bounded sequence of true secrecy rates and hence converges. It is further shown that its convergence point is a KKT point of the original SRM problem and, if the original problem is convex, this convergence point is globally-optimal, which is not necessarily the case in general. An interlacing property of the sequences of the true and approximate secrecy rates is established.

关键词： Convergence approximation algorithms Covariance matrices Optimization TV Null space Precoding Wiretap channel MIMO secrecy rate precoding artificial noise (AN) successive convex approximation

来源：评论

学校读者我要写书评

暂无评论

How Hard is Bribery in Elections with Randomly Selected Voters 21

How Hard is Bribery in Elections with Randomly Selected Vote...

引用

21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022

作者： Tao, Liangde Chen, Lin Xu, Lei Shi, Weidong Sunny, Ahmed Zaman, Md Mahabub Uz Zhejiang University Hangzhou China Texas Tech University Lubbock United States University of Texas Rio Grande Valley Edinburg United States University of Houston Houston United States

ISBN: (纸本)9781713854333

Many research works in computational social choice assume a fixed set of voters in an election and study the resistance of different voting rules against electoral manipulation. In recent years, however, a new technique known as random sample voting has been adopted in many multi-agent systems. One of the most prominent examples is blockchain. Many proof-of-stake based blockchain systems like Algorand will randomly select a subset of participants of the system to form a committee, and only the committee members will be involved in the decision of some important system parameters. This can be viewed as running an election where the voter committee (i.e., the voters whose votes will be counted) is randomly selected. It is generally expected that the introduction of such randomness should make the election more resistant to electoral manipulation, despite the lack of theoretical analysis. In this paper, we present a systematic study on the resistance of an election with a randomly selected voter committee against bribery. Since the committee is randomly generated, by bribing any fixed subset of voters, the designated candidate may or may not win. Consequently, we consider the problem of finding a feasible solution that maximizes the winning probability of the designated candidate. We show that for most voting rules, this problem becomes extremely difficult for the briber as even finding any non-trivial solution with non-zero objective value becomes NP-hard. However, for plurality and veto, there exists a polynomial time approximation scheme that computes a near-optimal solution efficiently. The algorithm builds upon a novel integer programming formulation together with techniques from n-fold integer programming, which may be of a separate interest. © 2022 International Foundation for Autonomous Agents and Multiagent Systems (***). All rights reserved

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Sublinear Time and Space algorithms for Correlation Clustering via Sparse-Dense Decompositions 13

Sublinear Time and Space Algorithms for Correlation Clusteri...

引用

13th Innovations in Theoretical Computer Science Conference, ITCS 2022

作者： Assadi, Sepehr Wang, Chen Department of Computer Science Rutgers University PiscatawayNJ United States

ISBN: (纸本)9783959772174

We present a new approach for solving (minimum disagreement) correlation clustering that results in sublinear algorithms with highly efficient time and space complexity for this problem. In particular, we obtain the following algorithms for n-vertex (+/−)-labeled graphs G: A sublinear-time algorithm that with high probability returns a constant approximation clustering of G in O(n log2 n) time assuming access to the adjacency list of the (+)-labeled edges of G (this is almost quadratically faster than even reading the input once). Previously, no sublinear-time algorithm was known for this problem with any multiplicative approximation guarantee. A semi-streaming algorithm that with high probability returns a constant approximation clustering of G in O(n log n) space and a single pass over the edges of the graph G (this memory is almost quadratically smaller than input size). Previously, no single-pass algorithm with o(n2) space was known for this problem with any approximation guarantee. The main ingredient of our approach is a novel connection to sparse-dense graph decompositions that are used extensively in the graph coloring literature. To our knowledge, this connection is the first application of these decompositions beyond graph coloring, and in particular for the correlation clustering problem, and can be of independent interest. © Sepehr Assadi and Chen Wang;licensed under Creative Commons License CC-BY 4.0

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On Lower Bounds of Approximating Parameterized k-Clique 49

On Lower Bounds of Approximating Parameterized k-Clique

引用

49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022

作者： Lin, Bingkai Ren, Xuandi Sun, Yican Wang, Xiuhan Nanjing University China Peking University Beijing China Tsinghua University Beijing China

ISBN: (纸本)9783959772358

Given a simple graph G and an integer k, the goal of the k-Clique problem is to decide if G contains a complete subgraph of size k. We say an algorithm approximates k-Clique within a factor g(k) if it can find a clique of size at least k/g(k) when G is guaranteed to have a k-clique. Recently, it was shown that approximating k-Clique within a constant factor is W[1]-hard [20]. We study the approximation of k-Clique under the Exponential Time Hypothesis (ETH). The reduction of [20] already implies an nΩ(√6 log k)-time lower bound under ETH. We improve this lower bound to nΩ(log k). Using the gap-amplification technique by expander graphs, we also prove that there is no ko(1) factor FPT-approximation algorithm for k-Clique under ETH. We also suggest a new way to prove the Parameterized Inapproximability Hypothesis (PIH) under ETH. We show that if there is no nO(log k k )-time algorithm to approximate k-Clique within a constant factor, then PIH is true. © Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang;licensed under Creative Commons License CC-BY 4.0

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A Parallel Hardware Implementation for 2-D Hierarchical Clustering Based on Fuzzy Logic

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 2021年第4期68卷 1428-1432页

作者： Cardarilli, Gian Carlo Di Nunzio, Luca Fazzolari, Rocco Panella, Massimo Re, Marco Rosato, Antonello Spano, Sergio Univ Roma Tor Vergata Dept Elect Engn I-00133 Rome Italy Sapienza Univ Rome Dept Informat Engn Elect & Telecommun I-00185 Rome Italy

In this brief we propose a novel hardware implementation for a bidimensional unconstrained hierarchical clustering method, based on fuzzy logic and membership functions. Unlike classical clustering approaches, this brief is based on an advanced algorithm that shows an intrinsic parallelism. Such parallelism can be exploited to design an efficient hardware implementation suitable for low-resources, low-power and high-computational demanding applications like smart-sensors and IoT devices. We validated our design by an extensive simulation campaign on well known 2D clustering datasets. Our solution shows the same clustering performances of the original algorithm despite the applied mathematical approximations and the small word-lengths used in the fixed point arithmetic.

关键词： Clustering algorithms Hardware Two dimensional displays Fuzzy logic approximation algorithms Circuits and systems Computer architecture Machine learning clustering hierarchical clustering low-power hardware acceleration field programmable gate arrays fuzzy logic membership functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：