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

2022 ACM SIGCOMM Workshop on Future of Internet Routing and Addressing, FIRA 2022

作者： Borhani, Mohammad Avgouleas, Ioannis Gurtov, Andrei Linköping University Linköping Sweden

ISBN: (纸本)9781450393287

Virtual Private LAN Services are becoming popular for securely connecting geographically dispersed devices to a common protected LAN network isolated from the rest of the Internet. Traditional IP routing protocols cannot provide such connectivity;thus an overlay network of encrypted HIP/IPsec tunnels can be used instead. However, the number of full-mesh tunnels between communicating devices grows exponentially to the number of devices thereby suggesting the investigation of alternatives. The introduction of relaying, which entails selecting a subset of hub routers to retain full-mesh connectivity, allows non-hub routers, the so-called spokes, to maintain connectivity via a hub. In this work, we study the effect of relay-based routing that minimizes the number of hubs, the connection cost between spokes and hubs, the cost of connecting hubs, and the hubs deployment cost. Additionally, we prove that this minimization problem is NP-hard and, thus, intractable for large scale networks. Therefore, we propose an algorithm with provable guarantees that provides an approximate but efficient solution. Initial simulation results indicate a reduction by more than 90% in the memory required for routing tables at the expense of a minor increase in the tunnel path length. © 2022 ACM.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Image Distortion Characterization due to Equivalent Monostatic approximation in Near-Field Bistatic SAR Imaging

引用

IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT 2020年第7期69卷 4898-4907页

作者： Manzoor, Zahra Al Qaseer, Mohammad Tayeb Donnell, Kristen M. Missouri Univ Sci & Technol Elect Engn Dept Rolla MO 65409 USA Iowa State Univ Elect Engn Dept Ames IA 50011 USA

The omega-k synthetic aperture radar (SAR) algorithm is a computationally efficient algorithm for near-field 3-D monostatic SAR imaging in nondestructive testing (NDT) applications. However, bistatic measurements are preferred in order to obtain high dynamic range, in particular when real-time imaging arrays are used. This article investigates the image distortion caused by using an equivalent monostatic imaging algorithm for bistatic measurements. Simulations and measurements at millimeter-wave frequencies in the Ka-band (26.5-40 GHz) are used to investigate the resultant image distortion. Furthermore, the image distortion is quantified through the root-mean-square (rms) error, which is calculated as a function of the bistatic transmitterreceiver separation distance, range, and noise power. Simulations and measurements are conducted for imaging using the raster scanning of a pair of antennas and for nonuniform imaging arrays. In addition, an approximate method for phase compensation is introduced to improve the image error from the monostatic approximation of bistatic measurement.

关键词： Distortion Imaging Receivers Transmitters Distortion measurement approximation algorithms Biomedical measurement Bistatic imaging configuration equivalent monostatic model image error phase-compensation method synthetic aperture radar (SAR) imaging

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies 36

Brief Announcement: Minimizing Congestion in Hybrid Demand-A...

引用

36th International Symposium on Distributed Computing, DISC 2022

作者： Dai, Wenkai Dinitz, Michael Foerster, Klaus-Tycho Schmid, Stefan Faculty of Computer Science Universität Wien Austria Computer Science Department Johns Hopkins University BaltimoreMD United States Computer Science Department Technische Universität Dortmund Germany TU Berlin Germany

ISBN: (纸本)9783959772556

Emerging reconfigurable optical communication technologies enable demand-aware networks: networks whose static topology can be enhanced with demand-aware links optimized towards the traffic pattern the network serves. This paper studies the algorithmic problem of how to jointly optimize the topology and the routing in such demand-aware networks, to minimize congestion. We investigate this problem along two dimensions: (1) whether flows are splittable or unsplittable, and (2) whether routing on the hybrid topology is segregated or not, i.e., whether or not flows either have to use exclusively either the static network or the demand-aware connections. For splittable and segregated routing, we show that the problem is 2-approximable in general, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we show an upper bound of O(log m/log log m) and a lower bound of Ω (log m/log log m) for polynomial-time approximation algorithms, where m is the number of static links. Under splittable (resp., unsplittable) and non-segregated routing, even for demands of a single source (resp., destination), the problem cannot be approximated better than Ω (cmax/cmin) unless P=NP, where cmax (resp., cmin) denotes the maximum (resp., minimum) capacity. It is still NP-hard for uniform capacities, but can be solved efficiently for a single commodity and uniform capacities. © Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A common approximation framework for early work, late work, and resource leveling problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第1期286卷 129-137页

作者： Gyorgyi, Peter Kis, Tamas Inst Comp Sci & Control Kende Str 13-17 H-1111 Budapest Hungary

We study the approximability of four scheduling problems on identical parallel machines. In the late work minimization problem, the jobs have arbitrary processing times and a common due date, and the objective is to minimize the late work, defined as the sum of the portion of the jobs done after the due date. A related problem is the maximization of the early work, defined as the sum of the portion of the jobs done before the due date. We describe a polynomial time approximation scheme for the early work maximization problem, and we extended it to the late work minimization problem after shifting the objective function by a positive value that depends on the problem data. We also prove an inapproximability result for the latter problem if the objective function is shifted by a constant which does not depend on the input. These results remain valid even if the number of the jobs assigned to the same machine is bounded. This leads to an extension of our approximation scheme to two variants of the resource leveling problem with unit time jobs, for which no approximation algorithm is known. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Scheduling late work minimization early work maximization resource leveling approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Average Sensitivity of the Knapsack Problem 30

Average Sensitivity of the Knapsack Problem

引用

30th Annual European Symposium on algorithms, ESA 2022

作者： Kumabe, Soh Yoshida, Yuichi The University of Tokyo Japan National Institute of Informatics Tokyo Japan

ISBN: (纸本)9783959772471

In resource allocation, we often require that the output allocation of an algorithm is stable against input perturbation because frequent reallocation is costly and untrustworthy. Varma and Yoshida (SODA'21) formalized this requirement for algorithms as the notion of average sensitivity. Here, the average sensitivity of an algorithm on an input instance is, roughly speaking, the average size of the symmetric difference of the output for the instance and that for the instance with one item deleted, where the average is taken over the deleted item. In this work, we consider the average sensitivity of the knapsack problem, a representative example of a resource allocation problem. We first show a (1 - ϵ)-approximation algorithm for the knapsack problem with average sensitivity O(ϵ-1 log ϵ-1). Then, we complement this result by showing that any (1 - ϵ)-approximation algorithm has average sensitivity Ω(ϵ-1). As an application of our algorithm, we consider the incremental knapsack problem in the random-order setting, where the goal is to maintain a good solution while items arrive one by one in a random order. Specifically, we show that for any ϵ > 0, there exists a (1 - ϵ)-approximation algorithm with amortized recourse O(ϵ-1 log ϵ-1) and amortized update time O(log n + fϵ), where n is the total number of items and fϵ > 0 is a value depending on ϵ. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Pseudorandom Generators, Resolution and Heavy Width 22

Pseudorandom Generators, Resolution and Heavy Width

引用

37th Computational Complexity Conference, CCC 2022

作者： Sokolov, Dmitry St. Petersburg State University Russia St. Petersburg Department of Steklov Mathematical Institute Russian Academy of Sciences Russia

ISBN: (纸本)9783959772419

Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson [2] we call a pseudorandom generator F : {0, 1}n → {0, 1}m hard for a propositional proof system P if P cannot efficiently prove the (properly encoded) statement b ∈/ Im(F) for any string b ∈ {0, 1}m. In [2] the authors suggested the "functional encoding" of the considered statement for Nisan–Wigderson generator that allows the introduction of "local" extension variables. These extension variables may potentially significantly increase the power of the proof system. In [2] authors gave a lower bound of exp [Ω (n2/m·22∆)] on the length of Resolution proofs where ∆ is the degree of the dependency graph of the generator. This lower bound meets the barrier for the restriction technique. In this paper, we introduce a "heavy width" measure for Resolution that allows us to show a lower bound of exp [n2/m2O(Ε∆)] on the length of Resolution proofs of the considered statement for the Nisan–Wigderson generator. This gives an exponential lower bound up to ∆:= log2−δ n (the bigger degree the more extension variables we can use). In [2] authors left an open problem to get rid of scaling factor 22∆ , it is a solution to this open problem. © Dmitry Sokolov

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

IoT Devices Signals Processing Based on Shepard Local approximation Operators Defined in Riesz MV-Algebras

引用

INFORMATICA 2020年第1期31卷 131-142页

作者： Noje, Dan Dzitac, Ioan Pop, Nicolae Tarca, Radu Univ Oradea Univ 1 Oradea 410087 Romania Primus Technol SRL Onestilor 3 Oradea 410248 Romania Aurel Vlaicu Univ Arad Elena Dragoi 2 Arad 310330 Romania Agora Univ Oradea Dept Econ Piata Tineretului 8 Oradea 410526 Romania Romanian Acad Inst Solid Mech Constantin Mille 15 Bucharest 10141 Romania

The Industry 4.0 and smart city solutions are impossible to be implemented without using IoT devices. There can be several problems in acquiring data from these IoT devices, problems that can lead to missing values. Without a complete set of data, the automation of processes is not possible or is not satisfying enough. The aim of this paper is to introduce a new algorithm that can be used to fill in the missing values of signals sent by IoT devices. In order to do that, we introduce Shepard local approximation operators in Riesz MV-algebras for one variable function and we structure the set of possible values of the IoT devices signals as Riesz MV-algebra. Based on these local approximation operators we define a new algorithm and we test it to prove that it can be used to fill in the missing values of signals sent by IoT devices.

关键词： IoT devices signal processing Shepard local approximation operators local approximation operators approximation algorithms Riesz MV-algebras vectorial MV-algebras

来源：评论

学校读者我要写书评

暂无评论

A Framework for Adversarially Robust Streaming algorithms

A Framework for Adversarially Robust Streaming Algorithms

引用

作者： Ben-Eliezer, Omri Jayaram, Rajesh Woodruff, David P. Yogev, Eylon Massachusetts Institute of Technology CambridgeMA02139 United States Google Research New YorkNY United States Carnegie Mellon University PittsburghPA15213 United States Bar-Ilan University Ramat Gan5290002 Israel

We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms;on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. In this work, we show that the answer is positive for various important streaming problems in the insertion-only model, including distinct elements and more generally Fp-estimation, Fp-heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust (1+ϵ)-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a poly(log n, 1/ϵ) multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a non-robust streaming algorithm into a robust one in various scenarios. © 2022 Association for Computing Machinery.

关键词： 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

来源：评论

学校读者我要写书评

暂无评论

Pricing Problems with Buyer Preselection

Pricing Problems with Buyer Preselection

引用

作者： Bilò, Vittorio Flammini, Michele Monaco, Gianpiero Moscardelli, Luca University of Salento Italy GSSI L’Aquila Italy University of L’Aquila Italy University of Chieti-Pescara Italy

We investigate the problem of preselecting a subset of buyers (also called agents) participating in a market so as to optimize the performance of stable outcomes. We consider four scenarios arising from the combination of two stability notions, namely market envy-freeness and agent envy-freeness, with the two state-of-the-art objective functions of social welfare and seller’s revenue. When insisting on market envy-freeness, we prove that the problem cannot be approximated within n1−Ε (with n being the number of buyers) for any Ε > 0, under both objective functions;we also provide approximation algorithms with an approximation ratio tight up to subpolynomial multiplicative factors for social welfare and the seller’s revenue. The negative result, in particular, holds even for markets with single-minded buyers. We also prove that maximizing the seller’s revenue is NP-hard even for a single buyer, thus closing a previous open question. Under agent envy-freeness and for both objective functions, instead, we design a polynomial time algorithm transforming any stable outcome for a market involving any subset of buyers into a stable outcome for the whole market without worsening its performance. This result creates an interesting middle-ground situation where, if on the one hand buyer preselection cannot improve the performance of agent envy-free outcomes, on the other one it can be used as a tool for simplifying the combinatorial structure of the buyers’ valuation functions in a given market. Finally, we consider the restricted case of multi-unit markets, where all items are of the same type and are assigned the same price. For these markets, we show that preselection may improve the performance of stable outcomes in all of the four considered scenarios, and design corresponding approximation algorithms. © 2022 AI Access Foundation. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：