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

BEATING THE INTEGRALITY RATIO FOR TOURS s-t- IN GRAPHS

SIAM JOURNAL ON COMPUTING 2023年第6期52卷 37-84页

作者： Traub, Vera Vygen, Jens Univ Bonn Res Inst Discrete Math D-53113 Bonn Germany Univ Bonn Hausdorff Ctr Math D-53113 Bonn Germany

Among various variants of the traveling salesman problem (TSP), the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomialtime algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3/2 -approximation algorithm in [A. Seb\H o and J. Vygen, Combinatorica, 34 (2014), pp. 597--629], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics).

关键词： traveling salesman problem integrality ratio approximation algorithm ear decomposition

来源：评论

学校读者我要写书评

暂无评论

FPGA Placement Using Space-Filling Curves: Theory Meets Practice

引用

ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS 2009年第2期9卷 12-12页

作者： Banerjee, Pritha Sur-Kolay, Susmita Bishnu, Arijit Das, Sandip Nandy, Subhas C. Bhattacharjee, Subhasis Indian Stat Inst Kolkata India Synopsis Pvt Ltd Bangalore Karnataka India

Research in VLSI placement, an NP-hard problem, has branched in two different directions. The first one employs iterative heuristics with many tunable parameters to produce a near-optimal solution but without theoretical guarantee on its quality. The other one considers placement as a graph-embedding problem and designs approximation algorithms with provable bounds on the quality of the solution. In this article, we aim at unifying the above two directions. First, we extend the existing approximation algorithms for graph embedding in 1D and 2D grid to those for hypergraphs, which typically model circuits to be placed on a FPGA. We prove an approximation bound of O(d root logn log log n) for 1D, that is, linear arrangement and O(d log nlog log n) for the 2D grid, where d is the maximum degree of hyperedges and n, the number of vertices in the hypergraph. Next, we propose an efficient method based on linear arrangement of the CLBs and the notion of space-filling curves for placing the configurable logic blocks (CLBs) of a netlist on island-style FPGAs with an approximation guarantee of O((4)root log n root kd log log n), where k is the number of nets. For the set of FPGA placement benchmarks, the running time is near linear in the number of CLBs thus allowing for scalability towards large circuits. We obtained a 33x speed-up, on average, with only 1.31x degradation in the quality of the solution compared to that produced by the popular FPGA tool VPR, thereby demonstrating the suitability of this very fast method for FPGA placement, with a provable performance guarantee.

关键词： FPGA placement approximation algorithm hypergraph linear arrangement space filling curve

来源：评论

学校读者我要写书评

暂无评论

Group fairness in non-monotone submodular maximization

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第3期45卷 88-88页

作者： Yuan, Jing Tang, Shaojie Univ North Texas Dept Comp Sci & Engn Denton TX USA Univ Texas Dallas Naveen Jindal Sch Management Richardson TX 75080 USA

Maximizing a submodular function has a wide range of applications in machine learning and data mining. One such application is data summarization whose goal is to select a small set of representative and diverse data items from a large dataset. However, data items might have sensitive attributes such as race or gender, in this setting, it is important to design fairness-aware algorithms to mitigate potential algorithmic bias that may cause over- or under- representation of particular groups. Motivated by that, we propose and study the classic non-monotone submodular maximization problem subject to novel group fairness constraints. Our goal is to select a set of items that maximizes a non-monotone submodular function, while ensuring that the number of selected items from each group is proportionate to its size, to the extent specified by the decision maker. We develop the first constant-factor approximation algorithms for this problem. We also extend the basic model to incorporate an additional global size constraint on the total number of selected items.

关键词： approximation algorithm Group fairness Submodular optimization

来源：评论

学校读者我要写书评

暂无评论

Radiation Constrained Fair Charging for Wireless Power Transfer

引用

ACM TRANSACTIONS ON SENSOR NETWORKS 2019年第2期15卷 15-15页

作者： Li, Lanlan Dai, Haipeng Chen, Guihai Zheng, Jiaqi Dou, Wanchun Wu, Xiaobing Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China Univ Canterbury Wireless Res Ctr Canterbury New Zealand

Recently, wireless power transfer technology (WPT) has attracted considerable attention and become a promising technology to prolong the lifetime of wireless sensor networks (WSNs) by providing perpetual energy to sensors. However, electromagnetic radiation (EMR) incurred by WPT is largely overlooked in most of the existing literature. In this article, we first propose and study the radiation constrained fair charging problem for WPT, i.e., maximizing the minimum utility of sensors by adjusting the power of wireless chargers with no EMR intensity at any location in the field exceeding a given threshold R-t. To address this problem, we first adopt an area discretization method to transform it from nonlinear to linear. Then, we propose four algorithms to deal with the reformulated problem, i.e., 1/3 and 1/4 approximation algorithms, Primal-Dual algorithm, and area division algorithm. In particular, the area division algorithm is not only fully distributed but also provably achieves an approximation ratio of (1 - epsilon). Further, we conduct extensive simulations and build a field testbed to verify our theoretical findings. Our simulation results show that the approximation ratios of the proposed algorithms hold;the Primal-Dual and area division algorithms have comparable performance of the optimal results and outperform baseline algorithms obviously.

关键词： Wireless rechargeable sensor networks electromagnetic radiation approximation algorithm distributed algorithm wireless power transfer

来源：评论

学校读者我要写书评

暂无评论

Channel modeling of wireless 3D-chip based on ray-tracing

引用

MICROELECTRONICS JOURNAL 2022年 119卷

作者： Ren, Chao Hou, Jingze Pan, Biao Univ Sci & Technol Beijing Sch Comp & Commun Engn & Shunde Grad Sch Beijing Peoples R China Univ Sci & Technol Beijing Beijing Peoples R China Beihang Univ Sch Integrated Circuit Sci & Engn MIIT Key Lab Spintron Beijing Peoples R China

The resource constraints and accuracy requirements for Internet of Things (IoT) memory chips need threedimensional (3D) monolithic integrated circuits, of which the increasing stack layers (currently more than 176) also cause excessive energy consumption and increasing wire length. In this paper, we propose and describe the channel modeling for wireless 3D chips based on ray-tracing. However, due to the reflection and refraction characteristics in each layer, the complex and diverse wireless paths in 3D chips add great difficulty to the channel characterization. To facilitate the modeling in massive layer wireless 3D chips based on ray-tracing, both boundary-less and boundary-constrained wireless 3D chips models are proposed based on ray-tracing, of which the channel gain can be obtained by a computational efficient approximate algorithm. These wireless 3D models with approximation algorithm can well characterize the wireless 3D chip channel in aspect of complete reflection and refraction characteristics, and avoid massive wired connections, high power consumption of cross-layer communication and high-complexity of 3D chips channel characterization. Numerical results show that: (1) The difference rate between the two models is lower than 0.001% (signal transmit through 20 layers);(2) the channel gain decreases sharply if refract time increases;and (3) the approximate algorithm can achieve an acceptable accuracy (error rate lower than 0.1%).

关键词： Ray-tracing Channel gain Three-dimensional chip approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal NP-Hardness of Approximating MAX k-CSPR

引用

THEORY OF COMPUTING 2022年 18卷 1-29页

作者： Manurangsi, Pasin Nakkiran, Preetum Trevisan, Luca Univ Calif Berkeley Berkeley CA USA Google Res Mountain View CA 94043 USA Univ Calif San Diego Halicioglu Data Sci Inst La Jolla CA 92093 USA Bocconi Univ Dept Decis Sci Comp Sci Milan Italy

We prove almost optimal hardness for MAX k-CSPR. In MAX k-CSPR, we are given a set of constraints, each of which depends on at most k variables. Each variable can take any value from 1, 2,. .., R. The goal is to find an assignment to variables that maximizes the number of satisfied constraints. We show that, for any k >= 2 and R >= 16, it is NP-hard to approximate MAX k- CSPR to within factor k(O(k))(logR)(k/2) =Rk-1. In the regime where 3 <= k = o(logR= log logR), this ratio improves upon Chan's O(k/Rk-2) factor NP-hardness of approximation of MAX k-CSPR (J. ACM 2016). Moreover, when k = 2, our result matches the best known hardness result of Khot, Kindler, Mossel and O'Donnell (SIAM J. Comp. 2007). We remark here that NPhardness of an approximation factor of 2(O(k)) log(kR)/Rk-1 is implicit in the (independent) work of Khot and Saket (ICALP 2015), which is better than our ratio for all k >= 3. In addition to the above hardness result, by extending an algorithm for MAX 2- CSPR by Kindler, Kolla and Trevisan (SODA 2016), we provide an Omega(logR/Rk-1)-approximation algorithm for MAX k-CSPR. Thanks to Khot and Saket's result, this algorithm is tight up to a factor of O(k(2)) when k <= R-O(1). In comparison, when 3 <= k is a constant, the previously best known algorithm achieves an O(k/Rk-1)-approximation for the problem, which is a factor of O(k logR) from the inapproximability ratio in contrast to our gap of O(k(2)).

关键词： constraint satisfaction hardness of approximation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

BETTER GUARANTEES FOR k-MEANS AND EUCLIDEAN k-MEDIAN BY PRIMAL-DUAL algorithmS

引用

SIAM JOURNAL ON COMPUTING 2020年第4期49卷 FOCS17-97-FOCS17-156页

作者： Ahmadian, Sara Norouzi-Fard, Ashkan Svensson, Ola Ward, Justin Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Ecole Polytech Fed Lausanne Sch Comp & Commun Sci CH-1015 Lausanne Switzerland

Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for k-means in Euclidean space with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of 9+epsilon, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of k-means and (2) satisfy the hard constraint that at most k clusters are selected without deteriorating the approximation guarantee. Our main result is a 6.357-approximation algorithm with respect to the standard linear programming (LP) relaxation. Our techniques are quite general, and we also show improved guarantees for k-median in Euclidean metrics and for a generalization of k-means in which the underlying metric is not required to be Euclidean.

关键词： k-means approximation algorithm primal-dual k-median LP-based algorithm clustering

来源：评论

学校读者我要写书评

暂无评论

Bounded mixed batch scheduling with job release dates and rejection

引用

OPERATIONS RESEARCH LETTERS 2024年 57卷

作者： Xu, Jun Huang, Yong-Xing Zhang, Daxing Lin, Ran Fan, Guo-Qiang Xidian Univ Guangzhou Inst Technol Adv Mfg Technol Innovat Ctr Guangzhou 510555 Peoples R China Northwestern Polytech Univ Sch Mech Engn Dept Ind Engn Xian 710072 Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Peoples R China Xidian Univ Sch Econ & Management Xian 710126 Peoples R China

This paper investigates a bounded mixed batch scheduling problem with job release dates and rejection. The machine processes a batch containing several jobs that their number does not exceed the machine capacity. For the case with a certain release date, we present a polynomial-time exact algorithm. For the case with a constant number of release dates, a pseudo-polynomial-time exact algorithm is proposed. For the general problem, we provide a 2-approximation algorithm and a polynomial-time approximation scheme. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Mixed batch scheduling Rejection penalty Exact algorithm approximation algorithm Polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Building a small and informative phylogenetic supertree

引用

INFORMATION AND COMPUTATION 2023年第1期294卷

作者： Jansson, Jesper Mampentzidis, Konstantinos Sandhya, T. P. Hong Kong Polytech Univ Dept Comp Hong Kong Peoples R China Kyoto Univ Grad Sch Informat Kyoto Japan Aarhus Univ Dept Comp Sci Aarhus Denmark Stockholm Univ Dept Math Stockholm Sweden

We combine two fundamental optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency and minimally resolved supertree into a new problem, which we call q-maximum rooted triplets consistency (q-MAXRTC). It takes as input a set R of rooted, binary phylogenetic trees with three leaves each and asks for a phylogenetic tree with exactly q internal nodes that contains the largest possible number of trees from R. We prove that q-MAXRTC is NP-hard to approximate within a constant, develop polynomial-time approximation algorithms for different values of q, and show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much branching information. To demonstrate the algorithmic advantage of using trees with few internal nodes, we also propose a new algorithm for computing the rooted triplet distance that is faster than the existing algorithms when restricted to such trees.

关键词： Phylogenetic tree Supertree Rooted triplet Consistency approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Auction algorithm sensitivity for multi-robot task allocation?

引用

AUTOMATICA 2023年第1期158卷

作者： Clinch, Katie Wood, Tony A. Manzie, Chris Univ New South Wales Sch Comp Sci & Engn Sydney NSW Australia Ecole Polytech Fed Lausanne SYCAMORE Lab Lausanne Switzerland Univ Melbourne Dept Elect & Elect Engn Melbourne Vic 3010 Australia

We consider the problem of finding a low-cost allocation and ordering of tasks between a team of robots in a d-dimensional, uncertain, landscape, and the sensitivity of this solution to changes in the cost *** algorithms have been shown to give a 2-approximation to the MIN$UM allocation problem. By analysing such an auction algorithm, we obtain intervals on each cost, such that any fluctuation of the costs within these intervals will result in the auction algorithm outputting the same solution.& COPY;2023 Published by Elsevier Ltd.

关键词： Sensitivity analysis Robustness Auction algorithm Minimum spanning tree Travelling salesman problem Task assignment approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：