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

A practical optimization framework for political redistricting: A case study in Arizona

SOCIO-ECONOMIC PLANNING SCIENCES 2024年 92卷

作者： Swamy, Rahul King, Douglas M. Ludden, Ian G. Dobbs, Kiera W. Jacobson, Sheldon H. Univ Illinois Dept Ind & Enterprise Syst Engn 104 S Mathews Ave Urbana IL 61801 USA Rose Hulman Inst Technol Dept Comp Sci & Software Engn 5500 Wabash Ave Terre Haute IN 47803 USA Univ Illinois Dept Comp Sci 201 N Goodwin Ave Urbana IL 61801 USA

Following the decennial census, each state in the U.S. redraws its congressional and state legislative district boundaries, which must satisfy various legal criteria. For example, Arizona's Constitution describes six legal criteria, including contiguity, population balance, competitiveness, compactness, and the preservation of communities of interest, political subdivisions and majority-minority districts, each of which is to be enforced "to the extent practicable". Optimization algorithms are well suited to draw district maps, although existing models and methods have limitations that inhibit their ability to draw legally -valid maps. Adapting existing optimization methods presents two major challenges: the complexity of modeling to achieve multiple and subjective criteria, and the computational intractability when dealing with large redistricting input graphs. In this paper, we present a multi -stage optimization framework tailored to redistricting in Arizona. This framework combines key features from existing methods, such as a multilevel algorithm that reduces graph input sizes and a larger local search neighborhood that encourages faster exploration of the solution space. This framework heuristically optimizes geographical compactness and political competitiveness while ensuring that other criteria in Arizona's Constitution are satisfied relative to existing norms. Compared to Arizona's enacted map (CD118) to be used until 2032, the most compact map produced by the algorithm is 41% more compact, and the most competitive map has five more competitive districts. To enable accessibility and to promote future research, we have created Optimap, a publicly accessible tool to interact with a part of this framework. Beyond the creation of these maps, this case study demonstrates the positive impact of adapting optimization -based methodologies for political redistricting in practice.

关键词： Political redistricting Optimization algorithms Local search multilevel algorithms Arizona Gerrymandering

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL RANDOMIZED multilevel algorithms FOR INFINITE-DIMENSIONAL INTEGRATION ON FUNCTION SPACES WITH ANOVA-TYPE DECOMPOSITION

引用

SIAM JOURNAL ON NUMERICAL ANALYSIS 2014年第3期52卷 1128-1155页

作者： Baldeaux, Jan Gnewuch, Michael Univ Technol Sydney Finance Discipline Grp Sydney NSW 2007 Australia Univ New S Wales Sch Math & Stat Sydney NSW Australia

In this paper, we consider the infinite-dimensional integration problem on weighted reproducing kernel Hilbert spaces with norms induced by an underlying function space decomposition of analysis of variance type. The weights model the relative importance of different groups of variables. We present new randomized multilevel algorithms to tackle this integration problem and prove upper bounds for their randomized error. Furthermore, we provide in this setting the first nontrivial lower error bounds for general randomized algorithms, which, in particular, may be adaptive or nonlinear. These lower bounds show that our multilevel algorithms are optimal. Our analysis refines and extends the analysis provided in [F. J. Hickernell, T. Muller-Gronbach, B. Niu, and K. Ritter, J. Complexity, 26 (2010), pp. 229-254], and our error bounds improve substantially on the error bounds presented there. As an illustrative example, we discuss the unanchored Sobolev space and employ randomized quasi-Monte Carlo multilevel algorithms based on scrambled polynomial lattice rules.

关键词： multilevel algorithms ANOVA decomposition randomized algorithms numerical integration reproducing kernel Hilbert spaces scrambled polynomial lattice rules

来源：评论

学校读者我要写书评

暂无评论

Improving the Scalability of Distributed Network Emulations: An Algorithmic Perspective

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2023年第4期20卷 4325-4339页

作者： Zhao, Huaiyi Zhang, Xinyi Wang, Yang Diao, Zulong Li, Yanbiao Xie, Gaogang Chinese Acad Sci Inst Comp Technol Beijing 100190 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China Chinese Acad Sci Comp Network Informat Ctr Beijing 100083 Peoples R China Purple Mt Labs Dept Future Networks Nanjing 211111 Peoples R China Univ Chinese Acad Sci Sch Comp Sci & Technol Beijing 100049 Peoples R China

By deploying virtualized network elements (hosts, switches, routers, links, etc.) on clusters of commodity machines, distributed network emulations (DNE) closely mimic the behaviors of network systems and provide real-time interactions and analysis for network service management. However, DNE encounters scalability challenges when faced with large network topologies. These challenges can be boiled down to the assignment problem: to which physical machine each virtualized network element should be assigned so that the largest possible network topology can be emulated? In this paper, we tackle this problem from an algorithmic perspective. We first propose TBR (topology balancing relaxation) as the relaxation of the assignment problem. TBR tries to maintain a balance of the hardware resource consumption, by minimizing the maximum inter-machine bandwidth. We further develop TBS (topology balancing solver), which combines mathematical techniques with multi-level algorithms to solve TBR efficiently. We integrate TBR and TBS into MaxiNet, a famous distributed network emulator. Experimental results show that with the same available physical resources, TBR and TBS can improve emulation scalability by up to 4.7x compared to baselines.

关键词： Distributed network emulations service assurance performance evaluations large-scale experimental platforms optimization theories multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

Infinite-Variate L²-Approximation with Nested Subspace Sampling 15th

Infinite-Variate L<SUP>2</SUP>-Approximation with Nested Sub...

引用

15th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC)

作者： Harsha, Kumar Gnewuch, Michael Wnuk, Marcin Osnabruck Univ Inst Math Albrechtrasse 28a D-49074 Osnabruck Germany

ISBN: (纸本)9783031597640;9783031597626;9783031597619

We consider L-2-approximation on weighted reproducing kernel Hilbert spaces of functions depending on infinitely many variables. We focus on unrestricted linear information, admitting evaluations of arbitrary continuous linear functionals. We distinguish between ANOVA and non-ANOVA spaces, where, by ANOVA spaces, we refer to function spaces whose norms are induced by an underlying ANOVA function decomposition. In ANOVA spaces, we provide an optimal algorithm to solve the approximation problem using linear information. We determine the upper and lower error bounds on the polynomial convergence rate of n-th minimal worst-case errors, which match if the weights decay regularly. For non-ANOVA spaces, we also establish upper and lower error bounds. Our analysis reveals that for weights with a regular and moderate decay behavior, the convergence rate of n-th minimal errors is strictly higher in ANOVA than in non-ANOVA spaces.

关键词： ANOVA decomposition Information-based complexity Reproducing kernel hilbert space weighted function spaces multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

Newton-type multilevel optimization method

引用

OPTIMIZATION METHODS & SOFTWARE 2022年第1期37卷 45-78页

作者： Ho, Chin Pang Kocvara, Michal Parpas, Panos City Univ Hong Kong Sch Data Sci Kowloon Hong Kong Peoples R China Univ Birmingham Sch Math Birmingham W Midlands England Acad Sci Czech Republ Inst Informat Theory & Automat Prague Czech Republic Imperial Coll London Dept Comp London England

Inspired by multigrid methods for linear systems of equations, multilevel optimization methods have been proposed to solve structured optimization problems. multilevel methods make more assumptions regarding the structure of the optimization model, and as a result, they outperform single-level methods, especially for large-scale models. The impressive performance of multilevel optimization methods is an empirical observation, and no theoretical explanation has so far been proposed. In order to address this issue, we study the convergence properties of a multilevel method that is motivated by second-order methods. We take the first step toward establishing how the structure of an optimization problem is related to the convergence rate of multilevel algorithms.

关键词： Newton's method multilevel algorithms multigrid methods unconstrained optimization

来源：评论

学校读者我要写书评

暂无评论

Fast Computation of Born-Approximated Multistatic Scattering

引用

IEEE TRANSACTIONS ON ULTRASONICS FERROELECTRICS AND FREQUENCY CONTROL 2021年第12期68卷 3637-3645页

作者： Elbaz, Eden Brick, Yaniv Ben Gurion Univ Negev Sch Elect & Comp Engn IL-8410501 Beer Sheva Israel

An algorithm for the fast computation of multistatic scattering patterns, produced by low-contrast inhomogeneous volumetric objects, which satisfy the Born approximation assumption, is presented. The algorithm relies on hierarchical interpolation and aggregation of optimally sampled phase-compensated partial contributions to the scattered field integral. The Born approximation enables the efficient simultaneous computation for ranges of incident and observation angles, as well as excitation frequencies. This leads to a reduction in the asymptotic computational complexity by several polynomial orders of the problem's acoustical size. The algorithm's error controllability and favorable computation time are demonstrated via representative examples.

关键词： Scattering Approximation algorithms Nonhomogeneous media Interpolation Integral equations Frequency control Observers Fast methods multilevel algorithms wave scattering

来源：评论

学校读者我要写书评

暂无评论

Gradient-Based Simulation Optimization algorithms via Multi-Resolution System Approximations

引用

INFORMS JOURNAL ON COMPUTING 2023年第3期35卷 633-651页

作者： Xu, Jingxu Zheng, Zeyu Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA

We propose gradient-based simulation-optimization algorithms to optimize systems that have complicated stochastic structure. The presence of complicated stochastic structure, such as the involvement of infinite-dimensional continuous-time stochastic processes, may cause the exact simulation of the system to be costly or even impossible. On the other hand, for a complicated system, one can sometimes construct a sequence of approximations at different resolutions, where the sequence has finer and finer approximation resolution but higher and higher cost to simulate. With the goal of optimizing the complicated system, we propose algorithms that strategically use the approximations with increasing resolution and higher simulation cost to construct stochastic gradients and perform gradient search in the decision space. To accommodate scenarios where approximations cause discontinuities and lead path-wise gradient estimators to have an uncontrollable bias, stochastic gradients for the proposed algorithms are constructed through finite difference. As a theory support, we prove algorithm convergence, convergence rate, and optimality of algorithm design under the assumption that the objective function for the complicated system is strongly convex, whereas no such assumptions are imposed on the approximations of the complicated system. We then present a multilevel version of the proposed algorithms to further improve convergence rates, when in addition the sequence of approximations can be naturally coupled.

关键词： gradient-based simulation-optimization algorithms approximating systems multilevel algorithms convergence rates

来源：评论

学校读者我要写书评

暂无评论

multilevel graph embedding

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2021年第3期28卷 e2326-e2326页

作者： Quiring, Benjamin Vassilevski, Panayot S. Northeastern Univ Dept Comp Sci Boston MA 02115 USA Lawrence Livermore Natl Lab Ctr Appl Sci Comp POB 808L-561 Livermore CA 94551 USA Portland State Univ Fariborz Maseeh Dept Math & Stat Portland OR 97207 USA

The goal of the present paper is the design of embeddings of a general sparse graph into a set of points inDouble-struck capital Rdfor appropriated >= 2. The embeddings that we are looking at aim to keep vertices that are grouped in communities together and keep the rest apart. To achieve this property, we utilize coarsening that respects possible community structures of the given graph. We employ a hierarchical multilevel coarsening approach that identifies communities (strongly connected groups of vertices) at every level. The multilevel strategy allows any given (presumably expensive) graph embedding algorithm to be made into a more scalable (and faster) algorithm. We demonstrate the presented approach on a number of given embedding algorithms and large-scale graphs and achieve speed-up over the methods in a recent paper.

关键词： embeddings graphs multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

A parallel hierarchical blocked adaptive cross approximation algorithm

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2020年第4期34卷 394-408页

作者： Liu, Yang Sid-Lakhdar, Wissam Rebrova, Elizaveta Ghysels, Pieter Li, Xiaoye Sherry Lawrence Berkeley Natl Lab Computat Res Div Scalable Solvers Grp Berkeley CA 94720 USA Lawrence Berkeley Natl Lab Computat Res Div Berkeley CA 94720 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90024 USA

This article presents a low-rank decomposition algorithm based on subsampling of matrix entries. The proposed algorithm first computes rank-revealing decompositions of submatrices with a blocked adaptive cross approximation (BACA) algorithm, and then applies a hierarchical merge operation via truncated singular value decompositions (H-BACA). The proposed algorithm significantly improves the convergence of the baseline ACA algorithm and achieves reduced computational complexity compared to the traditional decompositions such as rank-revealing QR. Numerical results demonstrate the efficiency, accuracy, and parallel scalability of the proposed algorithm.

关键词： Adaptive cross approximation singular value decomposition rank-revealing decomposition parallelization multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

Adaptive-multilevel BDDC algorithm for three-dimensional plane wave Helmholtz systems

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2021年 381卷 113011-113011页

作者： Peng, Jie Shu, Shi Wang, Junxian Zhong, Liuqiang South China Normal Univ Sch Math Sci Guangzhou 510631 Peoples R China Xiangtan Univ Sch Math & Computat Sci Xiangtan 411105 Peoples R China Xiangtan Univ Hunan Key Lab Computat & Simulat Sci & Engn Xiangtan 411105 Peoples R China

In this paper, we are concerned with the weighted plane wave least-squares (PWLS) method for three-dimensional Helmholtz equations, and develop the multi-level adaptive BDDC algorithms for solving the resulting discrete system. In order to form the adaptive coarse components, the local generalized eigenvalue problems for each common face and each common edge are carefully designed. The condition number of the two-level adaptive BDDC preconditioned system is proved to be bounded above by a user-defined tolerance and a constant which is dependent on the maximum number of faces and edges per subdomain and the number of subdomains sharing a common edge. The efficiency of these algorithms is illustrated on a benchmark problem. The numerical results show the robustness of our two-level adaptive BDDC algorithms with respect to the wave number, the number of subdomains and the mesh size, and illustrate that our multi-level adaptive BDDC algorithm can reduce the scale of the coarse problem and can be used to solve large wave number problems efficiently. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Helmholtz equation Plane wave discretization BDDC Adaptive constraints multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：