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

Seismic Image Dip Estimation by Multiscale Principal Component Analysis

IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING 2023年 61卷 1页

作者： Wu, Shaojiang Wang, Yibo Chinese Acad Sci Inst Geol & Geophys Key Lab Petr Resource Res Beijing 100029 Peoples R China Chinese Acad Sci Innovat Acad Earth Sci Beijing 100029 Peoples R China

Dip estimation of geological structures plays an important role in geophysical applications. Principal component analysis (PCA) is a common approach to estimating local dips by decomposing the local gradients of a seismic migration image and obtaining its principal eigenvector. However, PCA is difficult to obtain robust and high-resolution dip estimations for low signal-to-noise ratio (SNR) migration images, while multiscale schemes in digital image processing can achieve a better compromise between noise robustness and dip resolution. Therefore, we propose to adopt a multiscale PCA (MPCA) method coupled with a propagation-weight-based fusion mechanism for seismic dip estimation of low SNR migration image. MPCA consists of three steps: 1) constructing an image pyramid by repeating the low-pass filter from fine to coarse scales;2) estimating the dip using the PCA method at each scale of the image pyramid;and 3) fusing the multiscale dip estimations using propagation weights from coarse to fine scales. We test the MPCA method on an omnidirectional dip pattern and three seismic migration images and compare with the conventional PCA and multiscale methods. The results demonstrate that MPCA yields robust and high-resolution dip estimations for low SNR seismic migration images.

关键词： Estimation Principal component analysis Signal to noise ratio Image resolution Tensors Low-pass filters Mathematical models approximation algorithms estimation inverse problems mathematical model reliability

来源：评论

学校读者我要写书评

暂无评论

Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2021年第4期66卷 1401-1414页

作者： Abu-Affash, A. Karim Carmi, Paz Maheshwari, Anil Morin, Pat Smid, Michiel Smorodinsky, Shakhar Shamoon Coll Engn Software Engn Dept IL-84100 Beer Sheva Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Carleton Univ Sch Comp Sci Ottawa ON Canada Ben Gurion Univ Negev Dept Math IL-84105 Beer Sheva Israel

We consider a well-studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and a fixed parameter d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short) the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d = 1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n(1-epsilon), for any epsilon > 0. Moreover, it is known that, for any d = 2, it is NP-hard to approximate MaxDBS within a factor n(1/2-epsilon), for any epsilon > 0. In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems, and several geometric properties of unit disk graphs.

关键词： approximation algorithms Maximum diameter-bounded subgraph Unit disk graphs Fractional Helly theorem VC-dimension

来源：评论

学校读者我要写书评

暂无评论

Matchings under Preferences: Strength of Stability and Tradeoffs

引用

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 2021年第4期9卷 1–55页

作者： Chen, Jiehua Skowron, Piotr Sorge, Manuel TU Wien Vienna Austria Univ Warsaw Warsaw Poland

We propose two solution concepts for matchings under preferences: robustness and near stability. The former strengthens while the latter relaxes the classical definition of stability by Gale and Shapley (1962). Informally speaking, robustness requires that a matching must be stable in the classical sense, even if the agents slightly change their preferences. Near stability, however, imposes that a matching must become stable (again, in the classical sense) provided the agents are willing to adjust their preferences a bit. Both of our concepts are quantitative;together they provide means for a fine-grained analysis of the stability of matchings. Moreover, our concepts allow the exploration of tradeoffs between stability and other criteria of social optimality, such as the egalitarian cost and the number of unmatched agents. We investigate the computational complexity of finding matchings that implement certain predefined tradeoffs. We provide a polynomial-time algorithm that, given agent preferences, returns a socially optimal robust matching (if it exists), and we prove that finding a socially optimal and nearly stable matching is computationally hard.

关键词： Stable matchings concepts of stability NP-hardness parameterized complexity analysis exact algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults 18

Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faul...

引用

18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022

作者： Adjiashvili, David Hommelsheim, Felix Mühlenthaler, Moritz Schaudt, Oliver Department of Mathematics ETH Zürich Switzerland Department of Mathematics and Computer Science Universität Bremen Germany Laboratoire G-SCOP Grenoble INP Univ. Grenoble-Alpes France Department of Mathematics RWTH Aachen University Germany

ISBN: (纸本)9783959772365

The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k - 1 edges of the graph may fail. We extend the simple uniform failure model of the s-t EDP as follows: the edge set of the graph is partitioned into vulnerable, and safe edges, and a set of at most k vulnerable edges may fail, while safe edges do not fail. In particular we study the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest s-t Path problem in this non-uniform failure model as well as the Fault-Tolerant Flow (FTF) problem, the counterpart of s-t EDP. We present complexity results alongside exact and approximation algorithms for both problems. We emphasize the vast increase in complexity of the problems compared to s-t EDP. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimum Cost Feedback Selection in Structured Systems: Hardness and approximation Algorithm

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第12期65卷 5517-5524页

作者： Joshi, Aishwary Moothedath, Shana Chaporkar, Prasanna QE Secur LLP Gurugram 122002 India Univ Washington Seattle WA 98195 USA Indian Inst Technol Dept Elect Engn Mumbai 400076 Maharashtra India

This article deals with output feedback selection in linear time-invariant structured systems. We assume that the inputs and the outputs are dedicated, i.e., each input directly actuates a single state and each output directly senses a single state. Given a structured system with dedicated inputs and outputs and a cost matrix that denotes the cost of each feedback connection, our aim is to select a minimum cost set of feedback connections such that the closed-loop system satisfies arbitrary pole-placement. This problem is referred to as the optimal feedback selection problem for dedicated i/o. The optimal feedback selection problem for dedicated i/o is NP-hard and inapproximable to a constant factor of log n, where n denotes the system dimension. To this end, we propose an algorithm to find an approximate solution to the problem. The proposed algorithm consists of a potential function incorporated with a greedy scheme and attains a solution with a guaranteed approximation ratio. We consider two special network topologies of practical importance, referred to as back-edge feedback structure and hierarchical networks. For the first case, which is NP-hard and inapproximable to a multiplicative factor of log n, we provide a logn-approximate solution. For hierarchical networks, we give a dynamic programming based algorithm to obtain an optimal solution in polynomial time.

关键词： approximation algorithms Optimization Closed loop systems Dynamic programming Heuristic algorithms Dynamical systems Linear systems Arbitrary pole-placement hierarchical networks linear dynamical systems minimum cost feedback selection

来源：评论

学校读者我要写书评

暂无评论

Super oriented cycles in permutations

引用

COMPUTERS IN BIOLOGY AND MEDICINE 2023年 165卷 107426-107426页

作者： Jayakumar, P. Chitturi, Bhadrachalam Amrita Vishwa Vidyapeetham Dept Comp Sci & Applicat Amritapuri India Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

The degree of dissimilarity between genome sequences of homologous species is a measure of the evolutionary distance between them. It serves as a metric in the construction of phylogenetic trees, which depict the evolutionary relationships and common ancestry among different species. Given two genome sequences, evolutionary distance is determined by estimating the number of global mutations that transform one sequence to the other. The computation of the evolutionary distance is done by modelling a genome with the corresponding permutation. Global rearrangement operations such as transposition that model a particular genomic mutation are studied by employing a combinatorial structure known as a cycle graph of the corresponding permutation. A cycle in a cycle graph that has odd length is called an odd cycle. In the context of the problem of sorting by transpositions (SBT), a valid 2-move is a transposition that increases the number of odd cycles in the cycle graph by two. A super oriented cycle (SOC) is an odd cycle C where C and one of the resultant cycles admit valid 2-moves. The minimum number of mutations required to transform a species S into a related species T is the distance from S to T under that mutation. Christie opined that characterizing SOCs will improve the lower bound of the transposition distance. We characterize super oriented cycles. Equivalent transformations on permutations like reduction and (g,b)-split preserve the transposition distance of a given permutation and map SBT to the corresponding SBT on a transformed simpler permutation. We introduce merge, a novel equivalent transformation. These results have applications in computing transposition and other distances between related species.

关键词： approximation algorithms Mutations Permutations Sorting Super oriented cycles Transpositions Upper bound

来源：评论

学校读者我要写书评

暂无评论

Faber Polynomial Based approximations of Nonlinear Integrators for Electrodynamics

引用

IEEE JOURNAL ON MULTISCALE AND MULTIPHYSICS COMPUTATIONAL TECHNIQUES 2021年 6卷 41-49页

作者： Kleene, Hendrik Luong, Tommy Schulz, Dirk Tech Univ Dortmund Chair High Frequency Tech D-44227 Dortmund Germany

Faber polynomial based approximations of time dependent exponential integrators for the numerical solution of Maxwell's equations based on explicit algorithms are extended for the inclusion of nonlinear media so that multiphysical problems can be considered. For this purpose, appropriate exponential integrators, such as Lawson type and Rosenbrock type integrators are reviewed and investigated. The formulation with regard to Rosenbrock type integrators is extended to develop exponential integrators allowing the straightforward implementation of the resulting explicit algorithm and the application of large time step sizes opening up the potential for a parallel implementation. The Faber polynomial based approach for the approximation of the exponential integrator is utilized and as in the case of linear material models has an order of magnitude higher efficiency than comparable conventional methods, especially, when a high accuracy is required.

关键词： Jacobian matrices Mathematical model approximation algorithms Electrodynamics Nonlinear systems Media Electromagnetic propagation Exponential integrators Faber polynomial based expansion nonlinear media time dependent electromagnetic propagation

来源：评论

学校读者我要写书评

暂无评论

Gradient Methods With Dynamic Inexact Oracles

引用

IEEE CONTROL SYSTEMS LETTERS 2021年第4期5卷 1163-1168页

作者： Han, Shuo Univ Illinois Dept Elect & Comp Engn Chicago IL 60607 USA

We present a framework for generalizing the primal-dual gradient method, also known as the gradient descent ascent method, for solving convex-concave minimax problems. The framework is based on the observation that the primal-dual gradient method can be viewed as an inexact gradient method applied to the primal problem. Unlike the setting of traditional inexact gradient methods, the inexact gradient is computed by a dynamic inexact oracle, which is a discrete-time dynamical system whose output asymptotically approaches the exact gradient. For minimax problems, dynamic inexact oracles are capable of modeling a range of first-order methods for computing the gradient of the primal objective, which relies on solving the inner maximization problem. We provide a unified convergence analysis of gradient methods with dynamic inexact oracles and demonstrate its use in creating new accelerated primal-dual algorithms.

关键词： Gradient methods Heuristic algorithms Radio frequency Convergence approximation algorithms Acceleration Handheld computers Optimization algorithms stability of nonlinear systems

来源：评论

学校读者我要写书评

暂无评论

Electoral manipulation via influence: probabilistic model

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2023年第1期37卷 18-18页

作者： Tao, Liangde Chen, Lin Xu, Lei Xu, Shouhuai Gao, Zhimin Shi, Weidong Zhejiang Univ Hangzhou Peoples R China Texas Tech Univ Lubbock TX 79409 USA Kent State Univ Kent OH USA Univ Colorado Colorado Springs CO USA Univ Houston Houston TX USA

We consider a natural generalization of the fundamental electoral manipulation problem, where a briber can change the opinion or preference of voters through influence. This is motivated by modern political campaigns where candidates try to convince voters through media such as TV, newspaper, Internet. Compared with the classical bribery problem, we do not assume the briber will directly exchange money for votes from individual voters, but rather assume that the briber has a set of potential campaign strategies. Each campaign strategy represents some way of casting influence on voters. A campaign strategy has some cost and can influence a subset of voters. If a voter belongs to the audience of a campaign strategy, then he/she will be influenced. A voter will be more likely to change his/her opinion/preference if he/she has received influence from a larger number of campaign strategies. We model this through an independent activation model which is widely adopted in social science research and study the computational complexity. In this paper, we give a full characterization by showing NP-hardness results and establishing a near-optimal fixed-parameter tractable algorithm that gives a solution arbitrarily close to the optimal solution.

关键词： Computational social choice approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Mathematical Model To Calculate The Trajectories Of Electromagnetic Mill Operating Elements

Technical Electrodynamics

引用

Technical Electrodynamics 2021年第2期2021卷 26-34页

作者： Makarchuk, O. Calus, D. Moroz, V. Lviv Polytechnic National University 12 S. Bandera str. Lviv79013 Ukraine Czestochowa University of Technology Avenue 17 p.o. box 42-200 Czestochowa Poland

The purpose of the research under consideration is to develop a mathematical model to calculate the trajectories of the ferromagnetic operating elements (millstones) of an electromagnetic mill, moving in a rotating magnetic field under electrodynamic and hydrodynamic resistance forces being limited by the space of the mill’s working chamber. The millstone motion is described through the equations of plane motion of arbitrary-shaped two-dimensional body. The driving forces of this motion are determined on the basis of the approximation of the tabulated functions connecting the module and the orientation of the equivalent force applied to the millstone, with its position in the working chamber and composite MMF phase of mill inductor winding. These tabulated functions are derived from the estimation of the magnetic field inside a working chamber with millstones, in two-dimensional quasi-stationary approximation, using FEM analysis. The publication contains the approximation algorithm for these tabulated vector functions of a vector argument, mathematical statement of millstones trajectories calculating, and analysis of mathematical experiments results that make it possible to evaluate the adequacy of the model. The developed tool enables conducting quantitative analysis of grinding/mixing process and will help to establish relationships between the electromagnetic mill design parameters and its performance. References 21, figures 6. © 2021, Technical Electrodynamics. All Rights Reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：