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

Polynomial Time Learning-Augmented algorithms for NP-hard Permutation Problems

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Bampis, Evripidis Escoffier, Bruno Fotakis, Dimitris Patsilinakos, Panagiotis Xefteris, Michalis Sorbonne Université CNRS LIP6 ParisF-75005 France National Technical University of Athens Greece Archimedes Research Unit Athena RC Greece Université Paris-Dauphine Université PSL CNRS LAMSADE Paris75016 France

We consider a learning-augmented framework for NP-hard permutation problems. The algorithm has access to predictions telling, given a pair u, v of elements, whether u is before v or not in an optimal solution. Building on the work of Braverman and Mossel (SODA 2008), we show that for a class of optimization problems including scheduling, network design and other graph permutation problems, these predictions allow to solve them in polynomial time with high probability, provided that predictions are true with probability at least 1/2 + ϵ. Moreover, this can be achieved with a parsimonious access to the predictions. © 2025, CC BY.

关键词： optimization algorithms

PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Parmar, Mihir Liu, Xin Goyal, Palash Chen, Yanfei Le, Long Mishra, Swaroop Mobahi, Hossein Gu, Jindong Wang, Zifeng Nakhost, Hootan Baral, Chitta Lee, Chen-Yu Pfister, Tomas Palangi, Hamid Google United States Arizona State University United States

Recent agent frameworks and inference-time algorithms often struggle with complex planning problems due to limitations in verifying generated plans or reasoning and varying complexity of instances within a single task. Many existing methods for these tasks either perform task-level verification without considering constraints or apply inference-time algorithms without adapting to instance-level complexity. To address these limitations, we propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents. Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms–Best of N, Tree-of-Thought, and REBASE. In PlanGEN framework, the selection agent optimizes algorithm choice based on instance complexity, ensuring better adaptability to complex planning problems. Experimental results demonstrate significant improvements over the strongest baseline across multiple benchmarks, achieving state-of-the-art results on NATURAL PLAN (∼8%↑), OlympiadBench (∼4%↑), DocFinQA (∼7%↑), and GPQA (∼1%↑). Our key finding highlights that constraint-guided iterative verification improves inference-time algorithms, and adaptive selection further boosts performance on complex planning and reasoning problems. © 2025, CC BY.

关键词： optimization algorithms

On the non-submodularity of the problem of adding links to minimize the effective graph resistance

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Achterberg, Massimo A. Kooij, Robert E. Faculty of Electrical Engineering Mathematics and Computer Science Delft University of Technology P.O. Box 5031 Delft2600 GA Netherlands P.O. Box 96800 Den Haag2509 JE Netherlands

We consider the optimisation problem of adding k links to a given network, such that the resulting effective graph resistance is as small as possible. The problem was recently proven to be NP-hard, such that optimal solutions obtained with brute-force methods require exponentially many computation steps and thus are infeasible for any graph of realistic size. Therefore, it is common in such cases to use a simple greedy algorithm to obtain an approximation of the optimal solution. It is known that if the considered problem is submodular, the quality of the greedy solution can be guaranteed. However, it is known that the optimisation problem we are facing, is not submodular. For such cases one can use the notion of generalized submodularity, which is captured by the submodularity ratio γ. A performance bound, which is a function of γ, also exists in case of generalized submodularity. In this paper we give an example of a family of graphs where the submodularity ratio approaches zero, implying that the solution quality of the greedy algorithm cannot be guaranteed. Furthermore, we show that the greedy algorithm does not always yield the optimal solution and demonstrate that even for a small graph with 10 nodes, the ratio between the optimal and the greedy solution can be as small as 0.878. © 2025, CC BY.

关键词： optimization algorithms

A non-parametric optimal design algorithm for population pharmacokinetics

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Hovd, Markus Kryshchenko, Alona Neely, Michael N. Otalvaro, Julian Schumitzky, Alan Yamada, Walter M. Oslo University Hospital University of Oslo Norway California State University Channel Islands United States Children’s Hospital Los Angeles University of Southern California United States Children’s Hospital Los Angeles United States University of Southern California United States

This paper introduces a non-parametric estimation algorithm designed to effectively estimate the joint distribution of model parameters with application to population pharmacokinetics. Our research group has previously developed the non-parametric adaptive grid (NPAG) algorithm, which while accurate, explores parameter space using an ad-hoc method to suggest new support points. In contrast, the non-parametric optimal design (NPOD) algorithm uses a gradient approach to suggest new support points, which reduces the amount of time spent evaluating non-relevant points and by this the overall number of cycles required to reach convergence. In this paper, we demonstrate that the NPOD algorithm achieves similar solutions to NPAG across two datasets, while being significantly more efficient in both the number of cycles required and overall runtime. Given the importance of developing robust and efficient algorithms for determining drug doses quickly in pharmacokinetics, the NPOD algorithm represents a valuable advancement in nonparametric modeling. Further analysis is needed to determine which algorithm performs better under specific conditions. © 2025, CC BY.

关键词： optimization algorithms

Harmony Search Based Metaheuristic for the Index Tracking Problem 11th

学校读者我要写书评

暂无评论

Harmony Search Based Metaheuristic for the Index Tracking ...

11th Workshop on Engineering Applications, WEA 2024

作者： Ayón, Julián Antonio Díaz de Lourdes Sandoval Solis, María Velázquez, Rogelio González Ruiz, Maya Carrillo Garcés-Báez, Alfonso Benemérita Universidad Autónoma de Puebla Puebla72570 Mexico

ISBN: (纸本)9783031745973

The Index Tracking Problem involves the creation of an investment portfolio that accurately replicates the behavior of a market index. Being an NP-Hard optimization problem, it is well-suited for metaheuristic approaches. Drawing inspiration from the Harmony Search algorithm, the Harmony Search algorithm for Portfolio optimization is presented. This algorithm addresses the problem’s complex constraints by utilizing two search operators that effectively handle both the problem itself and the most difficult constraints, and it incorporates two population initialization strategies that aid in achieving convergence and can deal with problems of big size. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： optimization algorithms

Exponential Separation Criteria for Quantum Iterative Power algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Czégel, András Tóth, Boglárka G. Department of Computational Optimization University of Szeged Árpád tér 2 Szeged6720 Hungary

In the vast field of Quantum optimization, Quantum Iterative Power algorithms (QIPA) has been introduced recently with a promise of exponential speedup over an already established and well-known method, the variational Quantum Imaginary Time Evolution (varQITE) algorithm. Since the convergence and error of varQITE are known, the promise of QIPA also implied certain collapses in the complexity hierarchy — such as NP ⊆ BQP, as we show in our study. However the original article of QIPA explicitly states the algorithm does not cause any collapses. In this study we prove that these collapses indeed do not occur, and with that, prove that the promised exponential separation is practically unachievable. We do so by introducing criteria for the exponential separation between QIPA2 that uses a double exponential function and varQITE, and then showing how these criteria require certain properties in problem instances. After that we introduce a preprocessing step that enforces problems to satisfy these criteria, and then we show that the algorithmic error blows up exponentially for these instances, as there is an inverse polynomial term between speedup and the error. Despite the theoretical results, we also show that practically relevant polynomial enhancement is still possible, and show experimental results on a small problem instance, where we used our preprocessing step to achieve the improvement. © 2025, CC BY.

关键词： optimization algorithms

Learning Is a Kan Extension

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Pugh, Matthew Grundy, Jo Cirstea, Corina Harris, Nick

Previous work has demonstrated that efficient algorithms exist for computing Kan extensions and that some Kan extensions have interesting similarities to various machine learning algorithms. This paper closes the gap by proving that all error minimisation algorithms may be presented as a Kan extension. This result provides a foundation for future work to investigate the optimisation of machine learning algorithms through their presentation as Kan extensions. A corollary of this representation of error-minimising algorithms is a presentation of error from the perspective of lossy and lossless transformations of data. © 2025, CC BY.

关键词： optimization algorithms

AN IMPROVED OPTIMAL PROXIMAL GRADIENT ALGORITHM FOR NON-BLIND IMAGE DEBLURRING

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Wang, Qingsong Tong, Xiaojiao Xu, Shengze Zeng, Tieyong School of Mathematics and Computational Science Xiangtan University Hunan411105 China Department of Mathematics The Chinese University of Hong Kong Shatin Hong Kong

Image deblurring remains a central research area within image processing, critical for its role in enhancing image quality and facilitating clearer visual representations across diverse applications. This paper tackles the optimization problem of image deblurring, assuming a known blurring kernel. We introduce an improved optimal proximal gradient algorithm (IOptISTA), which builds upon the optimal gradient method and a weighting matrix, to efficiently address the non-blind image deblurring problem. Based on two regularization cases, namely the l1 norm and total variation norm, we perform numerical experiments to assess the performance of our proposed algorithm. The results indicate that our algorithm yields enhanced PSNR and SSIM values, as well as a reduced tolerance, compared to existing methods. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Solving the Best Subset Selection Problem via Suboptimal algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Singh, Vikram Sun, Min University of Central Oklahoma EdmondOK United States The University of Alabama TuscaloosaAL United States

Best subset selection in linear regression is well known to be nonconvex and computationally challenging to solve, as the number of possible subsets grows rapidly with increasing dimensionality of the problem. As a result, finding the global optimal solution via an exact optimization method for a problem with dimensions of 1000s may take an impractical amount of CPU time. This suggests the importance of finding suboptimal procedures that can provide good approximate solutions using much less computational effort than exact methods. In this work, we introduce a new procedure and compare it with other popular suboptimal algorithms to solve the best subset selection problem. Extensive computational experiments using synthetic and real data have been performed. The results provide insights into the performance of these methods in different data settings. The new procedure is observed to be a competitive suboptimal algorithm for solving the best subset selection problem for high-dimensional *** Codes 90C59, 65K05 © 2025, CC BY.

关键词： optimization algorithms