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

Coordinatewise domain scaling algorithm for M-convex function minimization

MATHEMATICAL PROGRAMMING 2005年第2期102卷 339-354页

作者： Tamura, A Kyoto Univ Math Sci Res Inst Kyoto 6068502 Japan

We present a polynomial time scaling algorithm for the minimization of an M-convex function. M-convex functions are nonlinear discrete functions with (poly)matroid structures, which are being recognized as playing a fundamental role in tractable cases of discrete optimization. The algorithm is applicable also to a variant of quasi M-convex functions.

关键词： discrete convex analysis M-convex function minimization scaling algorithm

来源：评论

学校读者我要写书评

暂无评论

A NEW scaling algorithm FOR THE MAXIMUM MEAN CUT PROBLEM

引用

algorithmICA 1994年第3期11卷 243-255页

作者： IWANO, K MISONO, S TEZUKA, S FUJISHIGE, S UNIV TSUKUBA INST SOCIOECON PLANNINGTSUKUBAIBARAKI 305JAPAN

We present a new scaling algorithm for the maximum mean cut problem. The mean of a cut is defined by the cut capacity divided by the number of area crossing the cut. The algorithm uses an approximate binary search and solves the circulation feasibility problem with relaxed capacity bounds. The maximum mean cut problem has recently been studied as a dual analogue of the minimum mean cycle problem in the framework of the minimum cost flow problem by Ervolina and McCormick. A network N = (G, lower, upper) with lower and upper are capacities is said to be delta-feasible if N has a feasible circulation when we relax the capacity bounds by delta;that is, we use (lower(a) - delta, upper(a) + delta) bounds instead of(lower(a), upper(a)) bounds for each are a is an element of A. During an approximate binary search we maintain two bounds, LB and UB, such that N is LB-infeasible and UB-feasible, and we reduce the interval size (LB, UB) by at least one-third at each iteration. For a graph with n vertices, m arcs, and integer capacities bounded by U, the running time of this algorithm is O(mn log(nU)). This time bound is better than the time achieved by McCormick and Ervolina under the similarity condition (that is, U = O(nO(0(1)))). Our algorithm can be naturally used for the circulation feasibility problem, and thus provides a new scaling algorithm for the minimum cut problem.

关键词： MAXIMUM MEAN CUT scaling algorithm CIRCULATION FEASIBILITY MINIMUM-COST CIRCULATION

来源：评论

学校读者我要写书评

暂无评论

A faster capacity scaling algorithm for minimum cost submodular flow

引用

MATHEMATICAL PROGRAMMING 2002年第1期92卷 119-139页

作者： Fleischer, L Iwata, S McCormick, ST Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1130033 Japan Univ British Columbia Fac Commerce & Business Adm Vancouver BC V6T 1Z2 Canada

We describe an O(n(4)h min{log U, n(2) log n}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds-Karp capacity seating algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails scaling a relaxation parameter delta, Capacities are relaxed by attaching a complete directed graph with uniform arc capacity delta in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along minimum cost paths of residual capacity at least delta. The shortest augmenting path subroutine we use is a variant of Dijkstra's algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow.

关键词： submodular function network flow scaling algorithm

来源：评论

学校读者我要写书评

暂无评论

A penalty-based scaling algorithm for the multi-period multi-product distribution planning problem

引用

ENGINEERING OPTIMIZATION 2017年第4期49卷 583-596页

作者： Hosseini, S. Ahmad Sahin, Guvenc Unluyurt, Tonguc Sabanci Univ Fac Engn & Nat Sci Istanbul Turkey Umea Univ Dept Math & Math Stat Umea Sweden

Multi-period multi-product distribution planning problems are depicted as multi-commodity network flow problems where parameters may change over time. The corresponding mathematical formulation is presented for a discrete time setting, and it can also be used as an approximation for a continuous time setting. A penalty-based method which employs a cost-scaling approach is developed to solve some auxiliary penalty problems aiming to obtain an optimal solution for the original problem. The experiments on both random instances and case study problems show that the algorithm finds good-quality solutions with reasonable computational effort.

关键词： Network flows distribution planning nonlinear programming scaling algorithm epsilon-optimality

来源：评论

学校读者我要写书评

暂无评论

Quantitative spatial upscaling of categorical information: The multi-dimensional grid-point scaling algorithm

引用

METHODS IN ECOLOGY AND EVOLUTION 2019年第12期10卷 2090-2104页

作者： Gann, Daniel Florida Int Univ Dept Biol Sci Miami FL 33199 USA Florida Int Univ Geog Informat Syst & Remote Sensing Ctr Miami FL 33199 USA

Categorical raster datasets often require upscaling to a lower spatial resolution to make them compatible with the scale of ecological analysis. When aggregating categorical data, two critical issues arise: (a) ignoring compositional information present in the high-resolution grid cells leads to high and uncontrolled loss of information in the scaled dataset;and (b) restricting classes to those present in the high-resolution dataset assumes validity of the classification scheme at the lower, aggregated resolution. I introduce a new scaling algorithm that aggregates categorical data while simultaneously controlling for information loss by generating a non-hierarchical, representative, classification system for the aggregated scale. The Multi-Dimensional Grid-Point (MDGP) scaling algorithm acknowledges the statistical constraints of compositional count data. In a neutral-landscape simulation study implementing a full-factorial design for landscape characteristics, scale factors and algorithm parameters, I evaluated consistency and sensitivity of the scaling algorithm. Consistency and sensitivity were assessed for compositional information retention (IRcmp) and class-label fidelity (CLF, the probability of recurring scaled class labels) for neutral random landscapes with the same properties. The MDGP-scaling algorithm consistently preserved information at a significantly higher rate than other commonly used algorithms. Consistency of the algorithm was high for IRcmp and CLF, but coefficients of variation of both metrics across landscapes varied most with class-abundance distribution. A diminishing return for IRcmp was observed with increasing class-label precision. Mean class-label recurrence probability was consistently above 75% for all simulated landscape types, scale factors and class-label precisions. The MDGP-scaling algorithm is the first algorithm that generates data-driven, scale-specific classification schemes while conducting spatial data aggregation. Consis

关键词： categorical raster data compositional count data multi-dimensional grid-point neutral landscape models scaling algorithm simplex simulation spatial scaling

来源：评论

学校读者我要写书评

暂无评论

Conjugate scaling algorithm for Fenchel-type duality in discrete convex optimization

引用

SIAM JOURNAL ON OPTIMIZATION 2002年第1期13卷 204-211页

作者： Iwata, S Shigeno, M Univ Tokyo Dept Math Engn & Informat Phys Tokyo 1138656 Japan Univ Tsukuba Inst Policy & Planning Sci Tsukuba Ibaraki 3058573 Japan

This paper presents a polynomial time algorithm for solving submodular flow problems with a class of discrete convex cost functions. This class of problems is a common generalization of the submodular flow and valuated matroid intersection problems. The algorithm adopts a new scaling technique that scales the discrete convex cost functions via the conjugacy relation. The algorithm can be used to find a pair of optima in the form of the Fenchel-type duality theorem in discrete convex analysis.

关键词： discrete convexity submodular flow scaling algorithm

来源：评论

学校读者我要写书评

暂无评论

A modified scaling algorithm for lp

引用

Optimization 1990年第5期21卷 709-721页

作者： Hettich, R. Ries, M. University Trier Dept. of Mathematics Germany

In this paper we consider the use of the scaling algorithm for LP for generating good starting vertices for the simplex method. To this end the original scaling algorithm has been modified on several points. For instance to enable the identification of a vertex variables which tend to zero are eliminated. Besides a vertex the algorithm also gives a LU-decomposition of a corresponding basismatrix. The numerical results obtained so far are encouraging, often the generated vertex is already the optimal one. © 1990, Taylor & Francis Group, LLC. All rights reserved.

关键词： Interior point methods Linear programming scaling algorithm

来源：评论

学校读者我要写书评

暂无评论

CartoonPlus: A new scaling algorithm for genomics data

引用

8th International Conference on Computational Science

作者： Jakubowska, Joanna Hunt, Ela Chalmers, Matthew Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland ETH Dept Comp Sci Zurich Switzerland

ISBN: (纸本)9783540693888

We focus on visualisation techniques used in genome browsers and report on a new technique, CartoonPlus, which improves the visual representation of data. We describe our use of smooth zooming and panning, and a new scaling algorithm and focus on options. CartoonPlus allows the users to see data not in original size but scaled, depending on the data type which is interactively chosen by the users. In VisGenome we have chosen genes as the basis for scaling. All genes have the same size and all other data is scaled in relationship to genes. Additionally, objects which are smaller than genes, such as micro array probes or markers, are scaled differently to reflect their partitioning into two categories: objects in a gene region and objects positioned between genes. This results in a significant legibility improvement and should enhance the understanding of genome maps.

关键词： genome visualisation visualisation techniques scaling algorithm large data sets

来源：评论

学校读者我要写书评

暂无评论

A scaling algorithm for weighted f-factors in general graphs 47

A scaling algorithm for weighted f-factors in general graphs

引用

47th International Colloquium on Automata, Languages, and Programming, ICALP 2020

作者： Duan, Ran He, Haoqing Zhang, Tianyi Institute for Interdisciplinary Information Sciences Tsinghua University Beijing China

ISBN: (纸本)9783959771382

We study the maximum weight perfect f-factor problem on any general simple graph G = (V, E, ω) with positive integral edge weights w, and n = |V |,m = |E|. When we have a function f : V → N+ on vertices, a perfect f-factor is a generalized matching so that every vertex u is matched to exactly f(u) different edges. The previous best results on this problem have running time O(mf(V )) [Gabow 2018] or Õ(W(f(V ))2.373)) [Gabow and Sankowski 2013], where W is the maximum edge weight, and f(V ) = Pu∈V f(u). In this paper, we present a scaling algorithm for this problem with running time Õ(mn2/3 log W). Previously this bound is only known for bipartite graphs [Gabow and Tarjan 1989]. The advantage is that the running time is independent of f(V ), and consequently it breaks the Ω(mn) barrier for large f(V ) even for the unweighted f-factor problem in general graphs. © Ran Duan, Haoqing He, and Tianyi Zhang;licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).

关键词： F-Factors General Graphs scaling algorithm

来源：评论

学校读者我要写书评

暂无评论

Nonlinear frequency scaling algorithm for high squint spotlight SAR data processing

引用

EURASIP JOURNAL ON ADVANCES IN SIGNAL PROCESSING 2008年第unknown期2008卷 1-8页

作者： Jin, Lihua Liu, Xingzhao Shanghai Jiao Tong Univ Dept Elect Engn Sch Elect Informat & Elect Engn Shanghai 200240 Peoples R China

This paper presents a new approach for the squint-mode spotlight SAR imaging. Like the frequency scaling algorithm, this method starts with the received signal dechirped in range. According to the geometry for the squint mode, the reference range of the dechirping function is defined as the range between the scene center and the synthetic aperture center. In our work, the residual video phase is compensated firstly to facilitate the following processing. Then the range-cell migration with a high-order range-azimuth coupling form is processed by a nonlinear frequency scaling operation, which is different from the original frequency scaling one. Due to these improvements, the algorithm can be used to process high squint SAR data with a wide swath and a high resolution. In addition, some simulation results are given at the end of this paper to demonstrate the validity of the proposed method. Copyright (c) 2008 L. Jin and X. Liu.

关键词： .Spotlight synthetic aperture scaling algorithm SAR Data Nonlinear Frequency High Squint squint mode residual video phase

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：