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

approximation algorithms for job scheduling with block-type conflict graphs

学校读者我要写书评

暂无评论

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

Efficient and Practical approximation algorithms for Advertising in Content Feeds 25

学校读者我要写书评

暂无评论

Efficient and Practical Approximation Algorithms for Adverti...

34th ACM Web Conference, WWW 2025

作者： Zhang, Guangyi Sarpe, Ilie Gionis, Aristides Shenzhen Technology University Shenzhen China KTH Royal Institute of Technology Stockholm Sweden

ISBN: (纸本)9798400712746

Content feeds provided by platforms such as X (formerly Twitter) and TikTok are consumed by users on a daily basis. In this paper, we revisit the native advertising problem in content feeds, initiated by Ieong et al. Given a sequence of organic items (e.g., videos or posts) relevant to a user’s interests or to an information search, the goal is to place ads within the organic content so as to maximize a reward function (e.g., number of clicks), while accounting for two considerations: (1) an ad can only be inserted after a relevant content item;(2) the users’ attention decays after consuming content or ads. These considerations provide a natural model for capturing both the advertisement effectiveness and the user experience. In this paper, we design fast and practical 2-approximation greedy algorithms for the associated optimization problem, improving over the best-known practical algorithm that only achieves an approximation factor of 4. Our algorithms exploit a counter-intuitive observation, namely, while top items are seemingly more important due to the decaying attention of the user, taking good care of the bottom items is key for obtaining improved approximation guarantees. We then provide the first comprehensive empirical evaluation on the problem, showing the strong empirical performance of our methods. © 2025 Copyright held by the owner/author(s).

关键词： approximation algorithms

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

学校读者我要写书评

暂无评论

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

Automating the Search for Small Hard Examples to approximation algorithms

学校读者我要写书评

暂无评论

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 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 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

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 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

GRASP and ILS Based Meta-Heuristic approximation algorithms for Optimal Virtual Network Synthesis (VNS) in Multi-AS Environment

学校读者我要写书评

暂无评论

GRASP and ILS Based Meta-Heuristic Approximation Algorithms ...

International Conference on Computing, Networking and Communications (ICNC)

作者： Yong Xue Alexander Brodsky Daniel Menasce George Mason University Fairfax Virginia USA

ISBN: (数字)9798350370997

ISBN: (纸本)9798350371000

Emerging Internet architecture utilizes a pluralistic architectural paradigm in which multiple virtual overlay service networks are built on top of the existing interconnected Autonomous System (multi-AS) networks across the world to satisfy diverse and ever-demanding service requirements from end users as well as emerging network applications. However, optimal provisioning and management of virtual networks in the multi-AS environment is still a challenging and unsolved problem. The problem has been extensively studied within the research community as a so-called multi-domain virtual network embedding (MD-VNE) optimization problem, but the current research results so far have been unsatisfactory and lack practical use. This paper proposes a bottom-up virtual network synthesis (VNS) approach to the MD-VNE problem in multi-AS network environment and formulates it into a combinatorial optimization problem. We then propose two trajectory-based meta-heuristic approximation algorithms based on Greedy Randomized Adaptive Search Procedure (GRASP) and Iterative Local Search (ILS) methods together with a simple Greedy Heuristic (GH)-based algorithm as approximate solutions to the multi-AS VNS optimization problem. Experiments with these three approximation algorithms were conducted, and their performances were analyzed quantitatively based on well-defined metrics. The analysis results show the feasibility of the developed approximation solutions for practical solutions to the MD-VNE problem.

关键词： Measurement Autonomous systems Heuristic algorithms Metaheuristics approximation algorithms Search problems Network synthesis