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

An Optimal Algorithm for Half-plane Hitting Set

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Liu, Gang Wang, Haitao Kahlert School of Computing University of Utah Salt Lake CityUT84112 United States

Given a set P of n points and a set H of n half-planes in the plane, we consider the problem of computing a smallest subset of points such that each half-plane contains at least one point of the subset. The previously best algorithm solves the problem in O(n3 log n) time. It is also known that Ω(n log n) is a lower bound for the problem under the algebraic decision tree model. In this paper, we present an O(n log n) time algorithm, which matches the lower bound and thus is optimal. Another virtue of the algorithm is that it is relatively simple. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Decentralised convex optimisation with probability-proportional-to-size quantization

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Pasechnyuk, D.A. Dvurechensky, P. Uribe, C.A. Gasnikov, A.V. Mohamed bin Zayed University of Artificial Intelligence United Arab Emirates Ivannikov Institute for System Programming the Russian Academy of Sciences Russia Weierstrass Institute for Applied Analysis and Stochastics Germany Rice University United States Moscow Institute of Physics and Technology Russia

Communication is one of the bottlenecks of distributed optimisation and learning. To overcome this bottleneck, we propose a novel quantization method that transforms a vector into a sample of components’ indices drawn from a categorical distribution with probabilities proportional to values at those components. Then, we propose a primal and a primal-dual accelerated stochastic gradient methods that use our proposed quantization, and derive their convergence rates in terms of probabilities of large deviations. We focus on affine-constrained convex optimisation and its application to decentralised distributed optimisation problems. To illustrate the work of our algorithm, we apply it to the decentralised computation of semi-discrete entropy regularized Wasserstein *** Codes 65K10 © 2025, CC BY.

关键词： optimization algorithms

Approximation algorithms for Optimal Hopsets

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Dinitz, Michael Koranteng, Ama Nazari, Yasamin

A hopset H with hopbound β and stretch α for a given graph G is a set of edges such that between every pair of vertices u and v there is a path with at most β hops in G∪H that approximates the distance between u and v up to a multiplicative stretch of α. Hopsets have found a wide range of applications in distance-based problems in various computational models since the 90s. More recently, there has been significant interest in understanding these fundamental objects from an existential and structural perspective. But all of this work takes a worst-case (or existential) point of view: How many edges do we need to add to satisfy a given hopbound and stretch requirement for any input graph? We initiate the study of the natural optimization variant of this problem: given a specific graph instance, what is the minimum number of edges that satisfy the hopbound and stretch requirements? We give approximation algorithms for a generalized hopset problem which, when combined with known existential bounds, lead to different approximation guarantees for various regimes depending on hopbound, stretch, and directed vs. undirected inputs. We complement our upper bounds with a lower bound that implies Label Cover hardness for directed hopsets/shortcut sets with hopbound at least 3. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Online Allocation with Multi-Class Arrivals: Group Fairness vs Individual Welfare

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zargari, Faraz Jazi, Hossein Nekouyan Sun, Bo Tan, Xiaoqi University of Alberta Canada University of Waterloo Canada

We introduce and study a multi-class online resource allocation problem with group fairness guarantees. The problem involves allocating a fixed amount of resources to a sequence of agents, each belonging to a specific group. The primary objective is to ensure fairness across different groups in an online setting. We focus on three fairness notions: one based on quantity and two based on utility. To achieve fair allocations, we develop two threshold-based online algorithms, proving their optimality under two fairness notions and near-optimality for the more challenging one. Additionally, we demonstrate a fundamental trade-off between group fairness and individual welfare using a novel representative function-based approach. To address this trade-off, we propose a set-aside multi-threshold algorithm that reserves a portion of the resource to ensure fairness across groups while utilizing the remaining resource to optimize efficiency under utility-based fairness notions. This algorithm is proven to achieve the Pareto-optimal trade-off. We also demonstrate that our problem can model a wide range of real-world applications, including network caching and cloud computing, and empirically evaluate our proposed algorithms in the network caching problem using real datasets. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

A Bias-Correction Decentralized Stochastic Gradient Algorithm with Momentum Acceleration

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Hu, Yuchen Chen, Xi Liu, Weidong Mao, Xiaojun School of Mathematical Sciences Shanghai Jiao Tong University Shanghai200240 China New York University New YorkNY10012 United States

Distributed stochastic optimization algorithms can handle large-scale data simultaneously and accelerate model training. However, the sparsity of distributed networks and the heterogeneity of data limit these advantages. This paper proposes a momentum-accelerated distributed stochastic gradient algorithm, referred to as Exact-Diffusion with Momentum (EDM), which can correct the bias caused by data heterogeneity and introduces the momentum method commonly used in deep learning to accelerate the convergence of the algorithm. We theoretically demonstrate that this algorithm converges to the neighborhood of the optimum sub-linearly irrelevant to data heterogeneity when applied to non-convex objective functions and linearly under the Polyak-Lojasiewicz condition (a weaker assumption than µ-strongly convexity). Finally, we evaluate the performance of the proposed algorithm by simulation, comparing it with a range of existing decentralized optimization algorithms to demonstrate its effectiveness in addressing data heterogeneity and network sparsity. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Connectivity-aware Synthesis of Quantum algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Dreier, Florian Fleckenstein, Christoph Aigner, Gregor Fellner, Michael Stahn, Reinhard Lanthaler, Martin Lechner, Wolfgang Institute for Theoretical Physics University of Innsbruck InnsbruckA-6020 Austria Parity Quantum Computing GmbH InnsbruckA-6020 Austria Parity Quantum Computing Germany GmbH Hamburg20095 Germany

We present a general method for the implementation of quantum algorithms that optimizes both gate count and circuit depth. Our approach introduces connectivity-adapted CNOT-based building blocks called Parity Twine chains. It outperforms all known state-of-the art methods for implementing prominent quantum algorithms such as the quantum Fourier transform or the Quantum Approximate optimization Algorithm across a wide range of quantum hardware, including linear, square-grid, hexagonal, ladder and all-to-all connected devices. For specific cases, we rigorously prove the optimality of our approach. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Use of modern algorithms for multi-parameter optimization and intelligent modelling of sustainable battery performance

学校读者我要写书评

暂无评论

JOURNAL OF ENERGY STORAGE 2023年 73卷

作者： Afzal, Asif Buradi, Abdulrajak Jilte, Ravindra Sundara, Vikram Shaik, Saboor Agbulut, Umit Alwetaishi, Mamdooh Saleel, C. Ahamed Visvesvaraya Technol Univ PA Coll Engn Dept Mech Engn Mangaluru 574153 India Chandigarh Univ Univ Ctr Res & Dev Dept Comp Sci & Engn Mohali 140413 Punjab India Nitte Meenakshi Inst Technol Dept Mech Engn Bangalore 560064 India Lovely Profess Univ Dept Mech Engn Phagwara 144411 Punjab India Univ Luxembourg Dept Engn Maison Nombre6 Ave Fonte L-4364 Esch Sur Alzette Luxembourg Vellore Inst Technol Sch Mech Engn Vellore 632014 Tamil Nadu India Duzce Univ Fac Engn Dept Mech Engn TR-81620 Duzce Turkiye Taif Univ Coll Engn Dept Civil Engn POB 11099 Taif 21944 Saudi Arabia King Khalid Univ Coll Engn Dept Mech Engn POB 394 Abha 61421 Saudi Arabia Duzce Univ Clean Energy Resources Applicat & Res Ctr TR-81620 Duzce Turkiye

The focus of this computational work is to predict and optimize the battery thermal performance indicators for its sustainable operation using different meta-heuristic optimization algorithms and machine learning models. The contribution of this work is two-fold, first, the heat removal ability from battery indicated by average Nusselt number (Nuavg) and hotspots (MaxT) to avoid battery thermal runaway are optimized as single objective optimization (SOO) and as multi-level objective optimization (MOO) problem. Second, intelligent algorithms: Gradient boosting (GB) algorithm and Gaussian process regressor (GPR) algorithm are used for modelling of Nuavg and MaxT. For SOO, Multi-verse optimization (MVO) and Grey wolf optimization (GWO) algorithms are used for individual battery performance indicators. Similarly, the enhanced version of MVO and GWO for MOO (MMVO and MGWO) algorithms is customized. Each algorithm is operated for five cycles and 100 iterations in each cycle of execution. In GB algorithm the effect of different loss functions and in GPR algorithm the effect of parameter alpha (alpha) is analyzed. SOO gives highest fitness of Nuavg and lowest hotspots occurrence from both the algorithms with same converged positions of operating parameters. MMVO and MGWO relatively provide lower Nuavg with MaxT in the same range of SOO. The MOO provides different set of particle positions compared to SOO. MGWO algorithm has outperformed in providing the best non-dominated solution. The GB and GPR algorithm are good enough for the forecasting of battery thermal parameters. GPR is even accurate, however the range of alpha is important during training and testing. The best Nuavg obtained from SOO using MVO algorithm is around 82.06 while MaxT is 0.34. The same from GWO algorithm is 82.05 and 0.33 respectively. MGWO algorithm in MOO provides Nuavg and MaxT around 75.57 and 0.34 while MMWO provides 66.76 and 0.33 respectively. GPR algorithm gives accuracy as close as 98 % for Ma

关键词： Battery temperature Heat Fitness functions Modelling optimization algorithms Predictions

A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Diakonikolas, Ilias Zarifis, Nikos UW-Madison United States

We study the problem of PAC learning γ-margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is known to be Θ(1 e /(γ2ǫ)). Prior computationally efficient algorithms for the problem incur sample complexity Õ(1/(γ4ǫ3)) and achieve 0-1 error of η + ǫ, where η e /(γ2ǫ2)), nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

A Descent-based method on the Duality Gap for solving zero-sum games

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Fasoulakis, Michail Markakis, Evangelos Roussakis, Giorgos Santorinaios, Christodoulos Royal Holloway University of London United Kingdom Archimedes RC Athens Greece Athens University of Economics and Business Greece Foundation for Research and Technology–Hellas Greece

We focus on the design of algorithms for finding equilibria in 2-player zero-sum games. Although it is well known that such problems can be solved by a single linear program, there has been a surge of interest in recent years for simpler algorithms, motivated in part by applications in machine learning. Our work proposes such a method, inspired by the observation that the duality gap (a standard metric for evaluating convergence in min-max optimization problems) is a convex function for bilinear zero-sum games. To this end, we analyze a descent-based approach, variants of which have also been used as a subroutine in a series of algorithms for approximating Nash equilibria in general non-zero-sum games. In particular, we study a steepest descent approach, by finding the direction that minimises the directional derivative of the duality gap function. Our main theoretical result is that the derived algorithms achieve a geometric decrease in the duality gap and improved complexity bounds until we reach an approximate equilibrium. Finally, we complement this with an experimental evaluation, which provides promising findings. Our algorithm is comparable with (and in some cases outperforms) some of the standard approaches for solving 0-sum games, such as OGDA (Optimistic Gradient Descent/Ascent), even with thousands of available strategies per player. © 2025, CC BY.

关键词： optimization algorithms