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

8th SIAM Symposium on Simplicity of algorithms, SOSA 2025

作者： Chen, Yijia Feng, Yi Laekhanukit, Bundit Liu, Yanlin Shanghai Jiao Tong University China Shanghai University of Finance and Economics China School of Mathematical Sciences Ocean University of China China

ISBN: (纸本)9781611978315

In the parameterized k-clique problem, or k-Clique for short, we are given a graph G and a parameter k ≥ 1. The goal is to decide whether there exist k vertices in G that induce a complete subgraph (i.e., a k-clique). This problem plays a central role in the theory of parameterized intractability as one of the first W[1]-complete problems. Existing research has shown that even an FPT-approximation algorithm for k-Clique with arbitrary ratio does not exist, assuming the Gap-Exponential-Time Hypothesis (Gap-ETH) [Chalermsook et al., FOCS'17 and SICOMP]. However, whether this inapproximability result can be based on the standard assumption of W[1] ≠ FPT remains unclear. In a breakthrough work of Bingkai Lin [STOC'21], any constant-factor approximation of k-Clique is shown to be W[1]-hard, and subsequently, the inapproximation ratio is improved to ko(1) in the work of Karthik C.S. and Khot [CCC'22], and independently in [Lin, Ren, Sun Wang;ICALP'22] (under the apparently stronger complexity assumption ETH). All the work along this line follows the framework developed by Lin, which starts from the k-vector-sum problem and requires some involved algebraic techniques. This paper presents an alternative framework for proving the W[1]-hardness of the ko(1)-FPT-approximation of k-Clique. Using this framework, we obtain a gap-producing self-reduction of k-Clique without any intermediate algebraic problem. More precisely, we reduce from (k, k − 1)-Gap Clique to (qk, qk−1)-Gap Clique, for any function q depending only on the parameter k, thus implying the ko(1)-inapproximability result when q is sufficiently large. Our proof is relatively simple and mostly combinatorial. At the core of our construction is a novel encoding of k-element subset stemmed from the theory of network coding and a (linear) Sidon set representation of a graph. Copyright © 2025 by SIAM.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Partitioning Friends Fairly 37

Partitioning Friends Fairly

引用

37th AAAI Conference on Artificial Intelligence (AAAI) / 35th Conference on Innovative Applications of Artificial Intelligence / 13th Symposium on Educational Advances in Artificial Intelligence

作者： Li, Lily Micha, Evi Nikolov, Aleksandar Shah, Nisarg Univ Toronto Dept Comp Sci Toronto ON Canada

ISBN: (纸本)9781577358800

We consider the problem of partitioning n agents in an undirected social network into k almost equal in size (differing by at most one) groups, where the utility of an agent for a group is the number of her neighbors in the group. The core and envy-freeness are two compelling axiomatic fairness guarantees in such settings. The former demands that there be no coalition of agents such that each agent in the coalition has more utility for that coalition than for her own group, while the latter demands that no agent envy another agent for the group they are in. We provide (often tight) approximations to both fairness guarantees, and many of our positive results are obtained via efficient algorithms.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

AirNN: A Featherweight Framework for Dynamic Input-Dependent approximation of CNNs

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2021年第10期40卷 2090-2103页

作者： Hemmat, Maedeh San Miguel, Joshua Davoodi, Azadeh Univ Wisconsin Dept Elect & Comp Engn 1415 Johnson Dr Madison WI 53706 USA

In this work, we propose AirNN, a novel framework which enables dynamic approximation of an already-trained convolutional neural network (CNN) in hardware during inference. AirNN enables input-dependent approximation of the CNN to achieve energy saving without much degradation in its classification accuracy at runtime. For each input, AirNN uses only a fraction of the CNN's weights based on that input (with the rest remaining 0) to conduct the inference. Consequently, energy saving is possible due to fewer number of fetches from off-chip memory as well as fewer multiplications for majority of the inputs. To achieve per-input approximation, we propose a clustering algorithm that groups similar weights in the CNN based on their importance, and design an iterative framework that decides dynamically how many clusters of weights should be fetched from off-chip memory for each individual input. We also propose new hardware structures to implement our framework on top of a recently proposed FPGA-based CNN accelerator. In our experiments with popular CNNs, we, on average, show 49% energy saving with less than 3% degradation in classification accuracy due to doing inference with only a fraction of the weights for the majority of the inputs. We also propose a greedy interleaving scheme, implemented in hardware, in order to improve the performance of the iterative procedure and compensate for its latency overhead.

关键词： Hardware Clustering algorithms approximation algorithms Neurons Degradation Neural networks Inference algorithms Approximate computation early termination input-dependent approximation low-energy design neural network accelerators

来源：评论

学校读者我要写书评

暂无评论

Network-Level Optimization for Unbalanced Power Distribution System: approximation and Relaxation

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2021年第5期36卷 4126-4139页

作者： Jha, Rahul Ranjan Dubey, Anamika Washington State Univ Sch Elect Engn & Comp Sci Pullman WA 99164 USA

The nonlinear programming (NLP) problem to solve distribution-level optimal power flow (D-OPF) poses convergence issues and does not scale well for unbalanced distribution systems. The existing scalable D-OPF algorithms either use approximations that are not valid for an unbalanced power distribution system, or apply relaxation techniques to the nonlinear power flow equations that do not guarantee a feasible power flow solution. In this paper, we propose scalable D-OPF algorithms that simultaneously achieve optimal and feasible solutions by solving multiple iterations of approximate, or relaxed, D-OPF subproblems of low complexity. The first algorithm is based on a successive linear approximation of the nonlinear power flow equations around the current operating point, where the D-OPF solution is obtained by solving multiple iterations of a linear programming (LP) problem. The second algorithm is based on the relaxation of the nonlinear power flow equations as conic constraints together with directional constraints, which achieves optimal and feasible solutions over multiple iterations of a second-order cone programming (SOCP) problem. It is demonstrated that the proposed algorithms are able to reach an optimal and feasible solution while significantly reducing the computation time as compared to an equivalent NLP D-OPF model for the same distribution system.

关键词： Mathematical model approximation algorithms Computational modeling Programming Power distribution Optimization Linear programming Iterative second order cone programming successive linear programming three-phase optimal power flow

来源：评论

学校读者我要写书评

暂无评论

approximation of the Constrained Joint Spectral Radius via Algebraic Lifting

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2021年第7期66卷 3386-3392页

作者： Xu, Xiangru Ackmese, Behcet Univ Wisconsin Dept Mech Engn Madison WI 53706 USA Univ Washington Dept Aeronaut & Astronaut Seattle WA 98195 USA

This article studies the constrained switching (linear) system which is a discrete-time switched linear system whose switching sequences are constrained by a deterministic finite automaton. The stability of a constrained switching system is characterized by its constrained joint spectral radius that is known to be difficult to compute or approximate. Using the semitensor product of matrices, the matrix-form expression of a constrained switching system is shown to be equivalent to that of a lifted arbitrary switching system. Then, the constrained joint/generalized spectral radius of a constrained switching system is proven to be equal to the joint/generalized spectral radius of its lifted arbitrary switching system which can be approximated by off-the-shelf algorithms.

关键词： Switches Switching systems Linear systems Automata approximation algorithms Eigenvalues and eigenfunctions Electronic mail Constrained joint spectral radius constrained switching systems semitensor product switched systems

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the balanced capacitated minimum spanning tree problem

引用

SCIENTIA IRANICA 2021年第3期28卷 1479-1492页

作者： Fallah, H. Didehvar, F. Rahmati, F. Amirkabir Univ Technol Dept Math & Comp Sci POB 15875-4418 Tehran Iran

Capacitated Minimum Spanning Tree Problem (CMSTP), a well-known combinatorial optimization problem, holds the central place in telecommunication network design. This problem involves finding a minimum cost spanning tree with an extra cardinality limitation on the orders of the subtrees incident to a certain root node. The Balanced Capacitated Minimum Spanning Tree Problem (BCMSTP) is a special case that aims to balance the orders of the subtrees. This problem is an NP-hard one and presents two approximation algorithms in this paper. By considering the maximum order of the subtrees Q, a (3 - 1/Q)-approximation algorithm was provided to find a balanced solution. This result was improved to a (2.5 + epsilon) approximation algorithm (for every given epsilon > 0) in the 2d-Euclidean spaces. Also, a Polynomial Time approximation Scheme (PTAS) was presented for CMSTP. (C) 2021 Sharif University of Technology. All rights reserved.

关键词： Capacitated minimum spanning tree problem Load balancing approximation algorithms PTAS

来源：评论

学校读者我要写书评

暂无评论

Soft Capacitated Two-Stage Stochastic Facility Location Problem 25th

Soft Capacitated Two-Stage Stochastic Facility Location Prob...

引用

25th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2024

作者： Guo, Yingying Li, Qiaoliang Zhang, Li School of Mathematics and Statistics Hunan Normal University Hunan Changsha410081 China College of Information and Intelligence Hunan Agricultural University Hunan Changsha410000 China

ISBN: (纸本)9789819642069

The two-stage stochastic facility location problem (SFL) has been extensively studied in the literature. However, as a crucial and worthwhile direction of SFL, the capacity variant of the SFL remains relatively underexplored. In this work, we give the first constant 3.7052-approximation ratio for the soft capacitated two-stage stochastic facility location problem (SCSFL). Initially, we present a 6-approximation algorithm for the SCSFL by utilizing the 3-approximation algorithm for the SFL. Subsequently, we enhance this algorithm through greedy improvement and cost scaling, achieving a significant reduction in the approximation ratio to 3.7052. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Simultaneous Perturbation Stochastic approximation-Based Consensus for Tracking Under Unknown-But-Bounded Disturbances

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2021年第8期66卷 3710-3717页

作者： Granichin, Oleg Erofeeva, Victoria Ivanskiy, Yury Jiang, Yuming St Petersburg State Univ Sci & Educ Ctr Math Robot & Artificial Intelligen St Petersburg 198504 Russia Norwegian Univ Sci & Technol NTNU Dept Informat Secur & Commun Technol NO-7491 Trondheim Norway

We consider a setup where a distributed set of sensors working cooperatively can estimate an unknown signal of interest, whereas any individual sensor cannot fulfill the task due to lack of necessary information diversity. This article deals with these kinds of estimation and tracking problems and focuses on a class of simultaneous perturbation stochastic approximation (SPSA)-based consensus algorithms for the cases when the corrupted observations of sensors are transmitted between sensors with communication noise and the communication protocol has to satisfy a prespecified cost constraints on the network topology. Sufficient conditions are introduced to guarantee the stability of estimates obtained in this way, without resorting to commonly used but stringent conventional statistical assumptions about the observation noise, such as randomness, independence, and zero mean. We derive an upper bound of the mean square error of the estimates in the problem of unknown time-varying parameters tracking under unknown-but-bounded observation errors and noisy communication channels. The result is illustrated by a practical application to the multisensor multitarget tracking problem.

关键词： Sensors approximation algorithms Optimization Noise measurement Perturbation methods Network topology Upper bound Arbitrary noise consensus algorithm distributed tracking multiagent networks randomized algorithm simultaneous perturbation stochastic approximation (SPSA) stochastic stability tracking performance unknown-but-bounded disturbances

来源：评论

学校读者我要写书评

暂无评论

Fast Greedy Subset Selection From Large Candidate Solution Sets in Evolutionary Multiobjective Optimization

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2022年第4期26卷 750-764页

作者： Chen, Weiyu Ishibuchi, Hisao Shang, Ke Southern Univ Sci & Technol Dept Comp Sci & Engn Guangdong Prov Key Lab Brain Inspired Intelligent Shenzhen 518055 Peoples R China

Subset selection plays an important role in the field of evolutionary multiobjective optimization (EMO). Especially, in an EMO algorithm with an unbounded external archive (UEA), subset selection is an essential post-processing procedure to select a prespecified number of solutions as the final result. In this article, we discuss the efficiency of greedy subset selection for the hypervolume, inverted generational distance (IGD), and IGD plus (IGD+) indicators. Greedy algorithms usually efficiently handle the subset selection. However, when a large number of solutions are given (e.g., subset selection from tens of thousands of solutions in a UEA), they often become time consuming. Our idea is to use the submodular property, which is known for the hypervolume indicator, to improve their efficiency. First, we prove that the IGD and IGD+ indicators are also submodular. Next, based on the submodular property, we propose an efficient greedy inclusion algorithm for each indicator. We demonstrate through computational experiments that the proposed algorithms are much faster than the standard greedy subset selection algorithms. The proposed algorithms also help the research on performance indicators.

关键词： Optimization Greedy algorithms Statistics Sociology approximation algorithms Evolutionary computation Clustering algorithms Evolutionary many-objective optimization evolutionary multiobjective optimization (EMO) performance indicators submodularity subset selection

来源：评论

学校读者我要写书评

暂无评论

Query-Efficient Black-Box Adversarial Attacks Guided by a Transfer-Based Prior

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2022年第12期44卷 9536-9548页

作者： Dong, Yinpeng Cheng, Shuyu Pang, Tianyu Su, Hang Zhu, Jun Tsinghua Univ Beijing Natl Res Ctr Informat Sci & Technol Tsinghua Bosch Joint Ctr Machine Learning Inst Artificial IntelligenceDept Comp Sci & Tech Beijing 100084 Peoples R China Pazhou Lab Guangzhou 510330 Peoples R China

Adversarial attacks have been extensively studied in recent years since they can identify the vulnerability of deep learning models before deployed. In this paper, we consider the black-box adversarial setting, where the adversary needs to craft adversarial examples without access to the gradients of a target model. Previous methods attempted to approximate the true gradient either by using the transfer gradient of a surrogate white-box model or based on the feedback of model queries. However, the existing methods inevitably suffer from low attack success rates or poor query efficiency since it is difficult to estimate the gradient in a high-dimensional input space with limited information. To address these problems and improve black-box attacks, we propose two prior-guided random gradient-free (PRGF) algorithms based on biased sampling and gradient averaging, respectively. Our methods can take the advantage of a transfer-based prior given by the gradient of a surrogate model and the query information simultaneously. Through theoretical analyses, the transfer-based prior is appropriately integrated with model queries by an optimal coefficient in each method. Extensive experiments demonstrate that, in comparison with the alternative state-of-the-arts, both of our methods require much fewer queries to attack black-box models with higher success rates.

关键词： Estimation Optimization Analytical models Numerical models Deep learning approximation algorithms Weight measurement Adversarial examples black-box attacks zeroth-order optimization query efficiency transferability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：