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

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Makarychev, Yury Ovsiankin, Max Tani, Erasmo Toyota Technological Institute ChicagoIL United States University of Chicago IL United States

ISBN: (纸本)9783959773225

We present polylogarithmic approximation algorithms for variants of the Shortest Path, Group Steiner Tree, and Group ATSP problems with vector costs. In these problems, each edge e has a vector cost ce ∈ R≥0. For a feasible solution – a path, subtree, or tour (respectively) – we find the total vector cost of all the edges in the solution and then compute the p-norm of the obtained cost vector (we assume that p ≥ 1 is an integer). Our algorithms for series-parallel graphs run in polynomial time and those for arbitrary graphs run in quasi-polynomial time. To obtain our results, we introduce and use new flow-based Sum-of-Squares relaxations. We also obtain a number of hardness results. © Yury Makarychev, Max Ovsiankin, and Erasmo Tani.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing 32

Approximation Algorithms for Hop Constrained and Buy-At-Bulk...

引用

32nd Annual European Symposium on algorithms, ESA 2024

作者： Chekuri, Chandra Jain, Rhea University of Illinois Urbana-ChampaignIL United States

ISBN: (纸本)9783959773386

We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [20, 58]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [20]. The rounding is based on recent results in hop-constrained oblivious routing [38], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to h-hop constrained network design for which we obtain LP-based bicriteria approximation algorithms. We also consider a fault-tolerant version of h-hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k − 1 edges can fail. This model has been considered in network design [42, 41, 7] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail. © Chandra Chekuri and Rhea Jain;licensed under Creative Commons License CC-BY 4.0.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Matroidal and Cardinal Generalizations of Stable Matching

Approximation Algorithms for Matroidal and Cardinal Generali...

引用

Symposium on Simplicity in algorithms (SOSA)

作者： Csaji, Gergely Kiraly, Tamas Yokoi, Yu Eotvos Lorand Univ Dept Operat Res MTA ELTE Momentum Matroid Optimizat Res Grp Budapest Hungary Eotvos Lorand Univ Dept Operat Res MTA ELTE Egervary Res Grp Budapest Hungary Natl Inst Informat Principles Informat Res Div Tokyo Japan

ISBN: (纸本)9781611977585

The Stable Marriage problem (SM), solved by the famous deferred acceptance algorithm of Gale and Shapley (GS), has many natural generalizations. If we allow ties in preferences, then the problem of finding a maximum solution becomes NP-hard, and the best known approximation ratio is 1.5 (McDermid ICALP 2009, PaluchWAOA 2011, Z. Kir ' aly MATCH-UP 2012), achievable by running GS on a cleverly constructed modified instance. Another elegant generalization of SM is the matroid kernel problem introduced by Fleiner (IPCO 2001), which is solvable in polynomial time using an abstract matroidal version of GS. Our main result is a simple 1.5-approximation algorithm for the matroid kernel problem with ties. We also show that the algorithm works for several other versions of stability defined for cardinal preferences, by appropriately modifying the instance on which GS is executed. The latter results are new even for the stable marriage setting.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Steiner Tree Augmentation Problems 34

Approximation Algorithms for Steiner Tree Augmentation Probl...

引用

34th ACM-SIAM Annual Symposium on Discrete algorithms (SODA)

作者： Ravi, R. Zhang, Weizhong Zlatin, Michael Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA

ISBN: (纸本)9781611977554

In the Steiner Tree Augmentation Problem (STAP), we are given a graph G = (V, E), a set of terminals R subset of V, and a Steiner tree T spanning R. The edges L := E \ E(T) are called links and have non-negative costs. The goal is to augment T by adding a minimum cost set of links, so that there are 2 edge-disjoint paths between each pair of vertices in R. This problem is a special case of the Survivable Network Design Problem, which can be approximated to within a factor of 2 using iterative rounding [13]. We give the first polynomial time algorithm for STAP with approximation ratio better than 2. In particular, we achieve an approximation ratio of (1.5 + epsilon). To do this, we employ the Local Search approach of [24] for the Tree Augmentation Problem and generalize their main decomposition theorem from links (of size two) to hyper-links. We also consider the Node-Weighted Steiner Tree Augmentation Problem (NW-STAP) in which the nonterminal nodes have non-negative costs. We seek a cheapest subset S subset of V \ R so that G[R boolean OR S] is 2-dge-connected. Using a result of Nutov [18], there exists an O(log vertical bar R vertical bar)-approximation for this problem. We provide an O(log(2)(vertical bar R vertical bar))-approximation algorithm for NW-STAP using a greedy algorithm leveraging the spider decomposition of optimal solutions.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy

Approximation Algorithms for Robot Tours in Random Fields wi...

引用

IEEE International Conference on Robotics and Automation (ICRA)

作者： Dulta, Shamak Wilde, Nils Tokekar, Pratap Smith, Stephen L. Univ Waterloo Dept Elect & Comp Engn Waterloo ON Canada Delft Univ Technol Cognit Robot Dept Delft Netherlands Univ Maryland Dept Comp Sci College Pk MD USA

ISBN: (纸本)9798350323658

We study the sample placement and shortest tour problem for robots tasked with mapping environmental phenomena modeled as stationary random fields. The objective is to minimize the resources used (samples or tour length) while guaranteeing estimation accuracy. We give approximation algorithms for both problems in convex environments. These improve previously known results, both in terms of theoretical guarantees and in simulations. In addition, we disprove an existing claim in the literature on a lower bound for a solution to the sample placement problem.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Fair Range Clustering 40

Approximation Algorithms for Fair Range Clustering

引用

40th International Conference on Machine Learning

作者： Hotegni, Sedjro S. Mahabadi, Sepideh Vakilian, Ali African Inst Math Sci Rwanda Kigali Rwanda Microsoft Res Redmond Redmond WA 98052 USA Toyota Technol Inst Chicago Chicago IL 60637 USA

This paper studies the fair range clustering problem in which the data points are from different demographic groups and the goal is to pick k centers with the minimum clustering cost such that each group is at least minimally represented in the centers set and no group dominates the centers set. More precisely, given a set of n points in a metric space (P, d) where each point belongs to one of the l different demographics (i.e., P = P-1 (sic) P-2 (sic) center dot center dot center dot (sic) P-l) and a set of l intervals [alpha(1), beta(1)], center dot center dot center dot, [alpha(1), beta(l)] on desired number of centers from each group, the goal is to pick a set of k centers C with minimum l(p)-clustering cost (i.e., (Sigma(v subset of P) d(v, C)(p))(1/p)) such that for each group i is an element of l, vertical bar C n P-i vertical bar is an element of [alpha(i), beta(i)]. In particular, the fair range l(p)-clustering captures fair range k-center, k-median and k-means as its special cases. In this work, we provide an efficient constant factor approximation algorithm for the fair range l(p)-clustering for all values of p is an element of [1, infinity).

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Maximizing Entanglement Routing Rate in Quantum Networks: approximation algorithms

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2025年第3期12卷 1939-1952页

作者： Nguyen, Dung H. P. Hunt, Ethan Horton, Dillon J. Nguyen, Tu N. Liu, Bing-Hong Natl Kaohsiung Univ Sci & Technol Dept Elect Engn Kaohsiung 80778 Taiwan Pham Dong Univ Fac Engn & Technol Quang Ngai 570000 Vietnam Kennesaw State Univ Dept Comp Sci Marietta GA 30060 USA

There will be a fast-paced shift from conventional network systems to novel quantum networks that are supported by the quantum entanglement and teleportation, key technologies of the quantum era, to enable secured data transmissions in the next-generation of the Internet. Despite this prospect, migration to quantum networks cannot happen all at once, especially when it comes to quantum routing. In this paper, we focus on the maximizing entanglement routing rate (MERR) problem, which aims to determine entangled routing paths for the maximum number of demands in the quantum network while meeting the network's fidelity. To tackle this problem, we first formulate the MERR problem using an integer linear programming (ILP) model. We then leverage the method of linear programming relaxation to devise two efficient algorithms, including the half-based rounding algorithm (HBRA) and the randomized rounding algorithm (RRA) with a provable approximation ratio for the objective function. Furthermore, to address the challenge of the combinatorial optimization problem in big scale networks, we also propose the path-length-based approach (PLBA) to solve the MERR problem. Finally, we evaluate the performance of our algorithms and show up the success of maximizing the entanglement routing rate.

关键词： Routing Quantum entanglement Qubit approximation algorithms Quantum mechanics Repeaters Quantum repeaters Network topology Topology Training Entanglement quantum repeater quantum networks

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for Several Positive Influence Dominating Set Problems in Social Networks

引用

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS 2025年

作者： Zhong, Hao Li, Weisheng Zhang, Qi Lin, Ronghua Tang, Yong South China Normal Univ Sch Comp Sci Guangzhou 510632 Guangdong Peoples R China Pazhou Lab Guangzhou 510330 Peoples R China Guangzhou Coll Commerce Sch Informat Technol & Engn Guangzhou 511363 Guangdong Peoples R China

Identifying positive influence dominating set (PIDS) with the smallest cardinality can produce positive effect with the minimal cost on a social network. The purpose of this article is to propose new approximation algorithms for the minimum PIDS problem and its variants such as the minimum connected PIDS and the minimum PIDS of multiplex networks, with the aim of finding target sets with smaller cardinality. Through the design of novel submodular potential function, we theoretically prove that new approximation algorithms yield approximation ratios with same order compared with existing algorithms. We further demonstrate the performance of our algorithm by showcasing its efficacy on several real-world and publicly available instances of social networks, thereby providing additional evidence that our proposed algorithm can identify PIDS with smaller cardinality.

关键词： approximation algorithms Social networking (online) Time complexity Heuristic algorithms Multiplexing Costs Electronic mail Drugs Training Technological innovation approximation algorithm connected positive influence dominating set (CPIDS) positive influence dominating set (PIDS) social networks submodular function

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions

引用

ALGORITHMICA 2024年第8期86卷 2575-2604页

作者： Bansal, Ishan Cheriyan, Joseph Grout, Logan Ibrahimpur, Sharat Cornell Univ Operat Res & Informat Engn Ithaca NY USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada London Sch Econ & Polit Sci Dept Math London England

We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Williamson et al. in Combinatorica 15(3):435-454, 1995. https://***/10.1007/BF01299747). Williamson et al. prove an approximation ratio of two for connectivity augmentation problems where the connectivity requirements can be specified by uncrossable functions. They state: "Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar. A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems." Our main result proves that the primal-dual algorithm of Williamson et al. achieves an approximation ratio of 16 for a class of functions that generalizes the notion of an uncrossable function. There exist instances that can be handled by our methods where none of the optimal dual solutions has a laminar support. We present three applications of our main result to problems in the area of network design. (1) A 16-approximation algorithm for augmenting a family of small cuts of a graph G. The previous best approximation ratio was O(log |V(G)|). (2) A 16 center dot (sic)k/u(min)(sic)-approximation algorithm for the Cap-k-ECSS problem which is as follows: Given an undirected graph G = (V, E) with edge costs c is an element of Q(>= 0)(E) and edge capacities u is an element of Z(>= 0)(E), find a minimum-cost subset of the edges F subset of E such that the capacity of any cut in (V, F) is at least k;u(min) (respectively, u(max)) denotes the minimum (respectively, maximum) capacity of an edge in E, and w.l.o.g. u(max) <= k. The previous best approximation ratio was min(O(log |V|), k, 2u(max)). (3) A 20-approximation algorithm for the model o

关键词： approximation algorithms Edge-connectivity of graphs f-connectivity problem Flexible graph connectivity Minimum cuts Network design Primal-dual method Small cuts

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for Index Coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第11期70卷 8266-8275页

作者： Chawin, Dror Haviv, Ishay Acad Coll Tel Aviv Yaffo Sch Comp Sci IL-61083 Tel Aviv Israel

The index coding problem is concerned with broadcasting encoded information to a collection of receivers in a way that enables each receiver to discover its required data based on its side information, which comprises the data required by some of the others. Given the side information map, represented by a graph in the symmetric case and by a digraph otherwise, the goal is to devise a coding scheme of minimum broadcast length. We present a general method for developing efficient algorithms for approximating the index coding rate for prescribed families of instances. As applications, we obtain polynomial-time algorithms that approximate the index coding rate of graphs and digraphs on n vertices to within factors of O(n/log(2)n) and O(n/log n) respectively. This improves on the approximation factors of O(n/log n) for graphs and O(n & sdot;log log n/log n) for digraphs achieved by Blasiak, Kleinberg, and Lubetzky. For the family of quasi-line graphs, we exhibit a polynomial-time algorithm that approximates the index coding rate to within a factor of 2. This improves on the approximation factor of O(n(2/3)) achieved by Arbabjolfaei and Kim for graphs on n vertices taken from certain sub-families of quasi-line graphs. Our approach is applicable for approximating a variety of additional graph and digraph quantities to within the same approximation factors. Specifically, it captures every graph quantity sandwiched between the independence number and the clique cover number and every digraph quantity sandwiched between the maximum size of an acyclic induced sub-digraph and the directed clique cover number.

关键词： approximation algorithms clique cover Index coding approximation algorithms clique cover

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：