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

arXiv 2022年

作者： Furmańczyk, Hanna Pikies, Tytus Sokolowska, Inka Turowski, Krzysztof Institute of Informatics Faculty of Mathematics Physics and Informatics University of Gdańsk Gdańsk80-309 Poland Department of Algorithms and System Modeling Gdańsk University of Technology Poland Theoretical Computer Science Department Jagiellonian University Poland

The problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory with methods relevant to graph coloring. Recently, cluster graphs and their extensions like block graphs were given additional attention. We complement hardness results provided by other researchers for block graphs by providing approximation algorithms. In particular, we provide a 2-approximation algorithm for P|G = block graph|Cmax and a PTAS for the case when the jobs are unit time in addition. In the case of uniform machines, we analyze two cases. The first one is when the number of blocks is bounded, i.e. Q|G = k-block graph|Cmax. For this case, we provide a PTAS, improving upon results presented by D. Page and R. Solis-Oba. The improvement is two-fold: we allow richer graph structure, and we allow the number of machine speeds to be part of the input. Due to strong NP-hardness of Q|G = 2-clique graph|Cmax, the result establishes the approximation status of Q|G = k-block graph|Cmax. The PTAS might be of independent interest because the problem is tightly related to the NUMERICAL k-DIMENSIONAL MATCHING WITH TARGET SUMS problem. The second case that we analyze is when the number of blocks is arbitrary, but the number of cut-vertices is bounded and jobs are of unit time. In this case, we present an exact algorithm. In addition, we present an FPTAS for graphs with bounded treewidth and a bounded number of unrelated machines. © 2022, CC BY.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Nash Social Welfare with Submodular Valuations: approximation algorithms and Integrality Gaps

arXiv

引用

arXiv 2025年

作者： Bei, Xiaohui Feng, Yuda Hu, Yang Li, Shi Zhang, Ruilong Division of Mathematical Sciences Nanyang Technological University Singapore School of Computer Science Nanjing University Nanjing China Institute for Interdisciplinary Information Sciences Tsinghua University Peking China Department of Mathematics Technical University of Munich Munich Germany

We study the problem of allocating items to agents such that the (un)weighted Nash social welfare (NSW) is maximized under submodular valuations. The best-known results for unweighted and weighted problems are the (4 + ϵ) approximation given by Garg, Husic, Li, Vega, and Vondrak [11] and the (233 + ϵ) approximation given by Feng, Hu, Li, and Zhang [8], respectively. For the weighted NSW problem, we present a (5.18 + ϵ)-approximation algorithm, significantly improving the previous approximation ratio and simplifying the analysis. Our algorithm is based on the same configuration LP in [8], but with a modified rounding algorithm. For the unweighted NSW problem, we show that the local search-based algorithm in [11] is an approximation of (3.914 + ϵ) by more careful analysis. On the negative side, we prove that the configuration LP for weighted NSW with submodular valuations has an integrality gap at least 2ln 2 − ϵ ≈ 1.617 − ϵ, which is slightly larger than the current best-known e/(e − 1) − ϵ ≈ 1.582 − ϵ hardness of approximation [12]. For the additive valuation case, we show an integrality gap of (e1/e − ϵ), which proves that the ratio of (e1/e + ϵ) [9] is tight for algorithms based on the configuration LP. For unweighted NSW with additive valuations, we show a gap of (21/4 − ϵ) ≈ 1.189 − ϵ, slightly larger than the current best-known p8/7 ≈ 1.069-hardness for the problem [10]. © 2025, CC BY-NC-ND.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

From Theory to Practice: Engineering approximation algorithms for Dynamic Orientation

arXiv

引用

arXiv 2025年

作者： Großmann, Ernestine van der Hoog, Ivor Reinstädtler, Henrik Rotenberg, Eva Schulz, Christian Vlieghe, Juliette Heidelberg University Germany Technical University of Denmark Denmark

Dynamic graph algorithms have seen significant theoretical advancements, but practical evaluations often lag behind. This work bridges the gap between theory and practice by engineering and empirically evaluating recently developed approximation algorithms for dynamically maintaining graph orientations. We comprehensively describe the underlying data structures, including efficient bucketing techniques and round-robin updates. Our implementation has a natural parameter λ, which allows for a trade-off between algorithmic efficiency and the quality of the solution. In the extensive experimental evaluation, we demonstrate that our implementation offers a considerable speedup. Using different quality metrics, we show that our implementations are very competitive and can outperform previous methods. Overall, our approach solves more instances than other methods while being up to 112 times faster on instances that are solvable by all methods compared. Copyright © 2025, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Complexity and approximation algorithms for Fixed Charge Transportation Problems

arXiv

引用

arXiv 2025年

作者： Chen, Yong Li, Shi Liang, Zihao Department of Mathematics Hangzhou Dianzi University Zhejiang Province Hangzhou China School of Computer Science Nanjing University Jiangsu Province Nanjing China

The Fixed Charge Transportation (FCT) problem models transportation scenarios where we need to send a commodity from n sources to m sinks, and the cost of sending a commodity from a source to a sink consists of a linear component and a fixed component. Despite extensive research on exponential time exact algorithms and heuristic algorithms for FCT and its variants, their approximability and computational complexity are not well understood. In this work, we initiate a systematic study of the approximability and complexity of these problems. When there are no linear costs, we call the problem the Pure Fixed Charge Transportation (PFCT) problem. We also distinguish between cases with general, sink-independent, and uniform fixed costs;we use the suffixes "-S" and "-U" to denote the latter two cases, respectively. This gives us six variants of the FCT problem. We give a complete characterization of the existence of O(1)-approximation algorithms for these variants. In particular, we give 2-approximation algorithms for FCT-U and PFCT-S, and a (6/5 + ϵ)-approximation for PFCT-U. On the negative side, we prove that FCT and PFCT are NP-hard to approximate within a factor of O(log2−ϵ(max{n, m})) for any constant ϵ > 0, FCT-S is NP-hard to approximate within a factor of c log(max{n, m}) for some constant c > 0, and PFCT-U is APX-hard. Additionally, we design an Efficient Parameterized approximation Scheme (EPAS) for PFCT when parameterized by the number n of sources, and an O(1/ϵ)-bicriteria approximation for the FCT problem, when we are allowed to violate the demand constraints for sinks by a factor of 1 ± ϵ. Copyright © 2025, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Automating the Search for Small Hard Examples to approximation algorithms

arXiv

引用

arXiv 2025年

作者： Sharma, Eklavya University of Illinois Urbana-Champaign United States

Given an approximation algorithm A, we want to find the input with the worst approximation ratio, i.e., the input for which A’s output’s objective value is the worst possible compared to the optimal solution’s objective value. Such hard examples shed light on the approximation algorithm’s weaknesses, and could help us design better approximation algorithms. When the inputs are discrete (e.g., unweighted graphs), one can find hard examples for small input sizes using brute-force enumeration. However, it’s not obvious how to do this when the input space is continuous, as in makespan minimization or bin packing. We develop a technique for finding small hard examples for a large class of approximation algorithms. Our algorithm works by constructing a decision tree representation of the approximation algorithm and then running a linear program for each leaf node of the decision tree. We implement our technique in Python, and demonstrate it on the longest-processing-time (LPT) heuristic for makespan minimization. Copyright © 2025, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for Three-Dimensional Knapsack

arXiv

引用

arXiv 2025年

作者： Jansen, Klaus Kar, Debajyoti Khan, Arindam Sreenivas, K.V.N. Tutas, Malte Kiel University Kiel Germany Indian Institute of Science Bengaluru India

We study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective is to find a non-overlapping axis-aligned packing (by translation) of the maximum profit subset of cuboids into the cube. The previous best approximation algorithm is due to Diedrich, Harren, Jansen, Thöle, and Thomas (2008), who gave a (7 + Ε)-approximation algorithm for 3DK and a (5 + Ε)-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant Ε > 0. Chlebík and Chlebíková (2009) showed that the problem does not admit an asymptotic polynomial-time approximation scheme. We provide an improved polynomial-time (139/29 + Ε) ≈ 4.794-approximation algorithm for 3DK and (30/7 + Ε) ≈ 4.286-approximation when rotations by 90 degrees are allowed. We also provide improved approximation algorithms for several variants such as the cardinality case (when all items have the same profit) and uniform profit-density case (when the profit of an item is equal to its volume). Our key technical contribution is container packing – a structured packing in 3D such that all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. We first show the existence of highly profitable container packings. Thereafter, we show that one can find near-optimal container packing efficiently using a variant of the Generalized Assignment Problem (GAP). © 2025, CC BY.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Parameterized and approximation algorithms for coverings points with segments in the plane

arXiv

引用

arXiv 2024年

作者： Kowalska, Katarzyna Pilipczuk, Michal University of Warsaw Poland

We study parameterized and approximation algorithms for a variant of Set Cover, where the universe of elements to be covered consists of points in the plane and the sets with which the points should be covered are segments. We call this problem Segment Set Cover. We also consider a relaxation of the problem called δ-extension, where we need to cover the points by segments that are extended by a tiny fraction, but we compare the solution’s quality to the optimum without extension. For the unparameterized variant, we prove that Segment Set Cover does not admit a PTAS unless P = NP, even if we restrict segments to be axis-parallel and allow 1/2-extension. On the other hand, we show that parameterization helps for the tractability of Segment Set Cover: we give an FPT algorithm for unweighted Segment Set Cover parameterized by the solution size k, a parameterized approximation scheme for Weighted Segment Set Cover with k being the parameter, and an FPT algorithm for Weighted Segment Set Cover with δ-extension parameterized by k and δ. In the last two results, relaxing the problem is probably necessary: we prove that Weighted Segment Set Cover without any relaxation is W[1]-hard and, assuming ETH, there does not exist an algorithm running in time f(k) · no(k/log k). This holds even if one restricts attention to axis-parallel segments. Copyright © 2024, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for Three-Dimensional Bin Packing

arXiv

引用

arXiv 2025年

作者： Kar, Debajyoti Khan, Arindam Rau, Malin Department of Computer Science and Automation Indian Institute of Science Bengaluru India Department of Mathematical Sciences Chalmers University of Technology University of Gothenburg GöteborgSE-412 96 Sweden

We study three fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3d-bp), 3D Strip Packing (3d-sp), and Minimum Volume Bounding Box (3d-mvbb), where given a set of 3D (rectangular) cuboids, the goal is to find an axis-aligned nonoverlapping packing of all cuboids. In 3d-bp, we need to pack the given cuboids into the minimum number of unit cube bins. In 3d-sp, we need to pack them into a 3D cuboid with a unit square base and minimum height. Finally, in 3d-mvbb, the goal is to pack into a cuboid box of minimum volume. It is NP-hard to even decide whether a set of rectangles can be packed into a unit square bin – giving an (absolute) approximation hardness of 2 for 3d-bp and 3d-sp. The previous best (absolute) approximation for all three problems is by Li and Cheng (SICOMP, 1990), who gave algorithms with approximation ratios of 13, 46/7, and 46/7 + Ε, respectively, for 3d-bp, 3d-sp, and 3d-mvbb. We provide improved approximation ratios of 6, 6, and 3 + Ε, respectively, for the three problems, for any constant Ε > 0. For 3d-bp, in the asymptotic regime, Bansal, Correa, Kenyon, and Sviridenko (Math. Oper. Res., 2006) showed that there is no asymptotic polynomial-time approximation scheme (APTAS) even when all items have the same height. Caprara (Math. Oper. Res., 2008) gave an asymptotic approximation ratio of T∞2 + Ε ≈ 2.86, where T∞ is the well-known Harmonic constant in Bin Packing. We provide an algorithm with an improved asymptotic approximation ratio of 3T∞/2 + Ε ≈ 2.54. Further, we show that unlike 3d-bp (and 3d-sp), 3d-mvbb admits an APTAS. © 2025, CC BY.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast approximation algorithms for scheduling uniform parallel batch machines with inclusive processing set restriction

Fast approximation algorithms for scheduling uniform paralle...

引用

Advanced algorithms and Control Engineering (ICAACE), International Conference on

作者： Yanyue Liang Lihong Zhang Shuguang Li School of Computer Science and Technology Shandong Technology and Business University Yantai China

ISBN: (数字)9798350361445

ISBN: (纸本)9798350361452

We address the problem on uniform parallel batch machines to minimize makespan where each job is restricted to a specific subset of machines, known as its processing set. Batch machines have diverse speeds and capacities. Each batch machine has the ability to concurrently process multiple jobs as long as the capacity allows. The length of a batch is defined as the largest length of all the jobs contained within it. We present fast approximation algorithms for inclusive processing set.

关键词： Schedules Control engineering Process control approximation algorithms Scheduling

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for Flexible Graph Connectivity and Capacitated Network Design

arXiv

引用

arXiv 2024年

作者： Bansal, Ishan Cheriyan, Joseph Khanna, Sanjeev Simmons, Miles Amazon BellevueWA United States Department of Combinatorics & Optimization University of Waterloo Canada University of Pennsylvania PhiladelphiaPA United States

We present improved approximation algorithms for some problems in the related areas of Flexible Graph Connectivity and Capacitated Network Design. In the (p, q)-Flexible Graph Connectivity problem, denoted (p, q)-FGC, the input is a graph G(V, E) where E is partitioned into safe and unsafe edges, and the goal is to find a minimum cost set of edges F such that the subgraph G′(V, F) remains p-edge connected upon removal of any q unsafe edges from F . In the related Cap-k-ECSS problem, we are given a graph G(V, E) whose edges have arbitrary integer capacities, and the goal is to find a minimum cost subset of edges F such that the graph G′(V, F) is k-edge connected. We obtain a 7-approximation algorithm for the (1, q)-FGC problem that improves upon the previous best (q + 1)-approximation. We also give an O(log k)-approximation algorithm for the Cap-k-ECSS problem, improving upon the previous best O(log n)-approximation whenever k = o(n). Both these results are obtained by using natural LP relaxations strengthened with the knapsack-cover inequalities, and then during the rounding process utilizing an O(1)-approximation algorithm for the problem of covering small cuts. We also show that the the problem of covering small cuts inherently arises in another variant of (p, q)-FGC. Specifically, we show O(1)-approximate reductions between the (2, q)-FGC problem and the 2-Cover Small Cuts problem where each small cut needs to be covered *** Codes 68W25, 90C27 © 2024, CC BY-NC-ND.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：