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

New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Berndt, Sebastian Brinkop, Hauke Jansen, Klaus Mnich, Matthias Stamm, Tobias University of Lübeck Institute for Theoretical Computer Science Lübeck Germany Kiel University Kiel Germany Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m · log(4m∆), where m is the number of constraints, and ∆ is the largest coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. To improve granularity, we analyze for the largest 1-norm Amax of any column of the constraint matrix, instead of ∆. We show a support size upper bound of s ≤ m · (log(3Amax) + √log(Amax)), by deriving a new bound on the -1 branch of the Lambert W function. Additionally, we provide a lower bound of mlog(Amax), proving our result asymptotically optimal. Furthermore, we give support bounds of the form s ≤ 2m · log(1.46Amax). These improve upon the previously best constants by Aliev. et. al. (SIAM J. Optim. 2018), because all our upper bounds hold equally with Amax replaced by √m∆. Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. First, we design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a (1 + Ε)-approximation for Q||Cmax on N jobs in time 2O(1/Ε log3 (1/Ε) log(log(1/Ε))) + O(N), which improves over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020) with run time 2O(1/Ε log4(1/Ε)) + NO(1). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation which greatly benefits from the small support. Second, we consider Q|HM|Cma

关键词： Integer programming

The Parameterized complexity of Network Microaggregation 37

学校读者我要写书评

暂无评论

The Parameterized Complexity of Network Microaggregation

37th AAAI Conference on Artificial Intelligence, AAAI 2023

作者： Blažej, Václav Ganian, Robert Knop, Dušan Pokorný, Jan Schierreich, Šimon Simonov, Kirill Faculty of Information Technology Czech Technical University in Prague Prague Czech Republic Algorithms and Complexity Group Technische Universität Wien Vienna Austria Hasso Plattner Institute University of Potsdam Postdam Germany

ISBN: (纸本)9781577358800

Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network. Copyright © 2023, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Parameterization

Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Kulik, Ariel Mnich, Matthias Shachnai, Hadas CISPA Helmholtz Center for Information Security Germany Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Computer Science Department Technion Haifa Israel

We study the d-dimensional Vector Bin Packing (dVBP) problem, a generalization of Bin Packing with central applications in resource allocation and scheduling. In dVBP, we are given a set of items, each of which is characterized by a d-dimensional volume vector;the objective is to partition the items into a minimum number of subsets (bins), such that the total volume of items in each subset is at most 1 in each dimension. Our main result is an asymptotic approximation algorithm for dVBP that yields a ratio of (1+ln d−χ(d)+Ε) for all d ∈ N and any Ε > 0;here, χ(d) is some strictly positive function. This improves upon the best known asymptotic ratio of (1 + ln d + Ε) due to Bansal, Caprara and Sviridenko (SICOMP 2010) for any d > 3. By slightly modifying our algorithm to include an initial matching phase and applying a tighter analysis we obtain an asymptotic approximation ratio of (4/3 + Ε) for the special case of d = 2, thus substantially improving the previous best ratio of (3/2 + Ε) due to Bansal, Eliáš and Khan (SODA 2016). Our algorithm iteratively solves a configuration LP relaxation for the residual instance (from previous iterations) and samples a small number of configurations based on the solution for the configuration LP. While iterative rounding was already used by Karmarkar and Karp (FOCS 1982) to establish their celebrated result for classic (one-dimensional) Bin Packing, iterative randomized rounding is used here for the first time in the context of (Vector) Bin Packing. Our results show that iterative randomized rounding is a powerful tool for approximating dVBP, leading to simple algorithms with improved approximation guarantees. Copyright © 2022, The Authors. All rights reserved.

关键词： Vectors

Recent advances in practical data reduction

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Abu-Khzam, Faisal Lamm, Sebastian Mnich, Matthias Noe, Alexander Schulz, Christian Strash, Darren Lebanese American University Lebanon Karlsruhe Institute of Technologie Germany Hamburg University of Technology Institute for Algorithms and Complexity Germany University of Vienna Austria Heidelberg University Germany

Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has resulted in an algorithmic toolbox that is by now well-established. However, these theoretical algorithmic ideas have received very little attention from the practical perspective. We survey recent trends in data reduction engineering results for selected problems. Moreover, we describe concrete techniques that may be useful for future implementations in the area and give open problems and research questions. Copyright © 2020, The Authors. All rights reserved.

关键词： Data reduction

Circumference of essentially 4-connected planar triangulations

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Fabrici, Igor Harant, Jochen Mohr, Samuel Schmidt, Jens M. Institute of Mathematics P.J. Šafárik University Košice Slovakia Institute of Mathematics Ilmenau University of Technology Germany Institute for Algorithms and Complexity Hamburg University of Technology Germany

A 3-connected graph G is essentially 4-connected if, for any 3-cut S ⊆ V (G) of G, at most one component of G − S contains at least two vertices. We prove that every essentially 4-connected maximal planar graph G on n vertices contains a cycle of length at least 32 (n + 4);moreover, this bound is *** Codes 05C38, 05C10 Copyright © 2021, The Authors. All rights reserved.

关键词： Graph theory

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kaul, Matthias Mnich, Matthias Molter, Hendrik Universität Bonn Germany Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Department of Computer Science Ben-Gurion University of the Negev Be’er-Sheva Israel

We study the fundamental scheduling problem 1 | rj | P wjUj: schedule a set of n jobs with weights, processing times, release dates, and due dates on a single machine, such that each job starts after its release date and we maximize the weighted number of jobs that complete execution before their due date. Problem 1 | rj | P wjUj generalizes both Knapsack and Partition, and the simplified setting without release dates was studied by Hermelin et al. [Annals of Operations Research, 2021] from a parameterized complexity viewpoint. Our main contribution is a thorough complexity analysis of 1 | rj | P wjUj in terms of four key problem parameters: the number p# of processing times, the number w# of weights, the number d# of due dates, and the number r# of release dates of the jobs. 1 | rj | P wjUj is known to be weakly para-NP-hard even if w# + d# + r# is constant, and Heeger and Hermelin [ESA, 2024] recently showed (weak) W[1]-hardness parameterized by p# or w# even if r# is constant. Algorithmically, we show that 1 | rj | P wjUj is fixed-parameter tractable parameterized by p# combined with any two of the remaining three parameters w#, d#, and r#. We further provide pseudo-polynomial XP-time algorithms for parameter r# and d#. To complement these algorithms, we show that 1 | rj | P wjUj is (strongly) W[1]-hard when parameterized by d# + r# even if w# is constant. Our results provide a nearly complete picture of the complexity of 1 | rj | P wjUj for p#, w#, d#, and r# as parameters, and extend those of Hermelin et al. [Annals of Operations Research, 2021] for the problem 1 || P wjUj without release dates. Copyright © 2024, The Authors. All rights reserved.

关键词： Parameterization

Can quantum search accelerate evolutionary algorithms? 10

学校读者我要写书评

暂无评论

Can quantum search accelerate evolutionary algorithms?

12th Annual Genetic and Evolutionary Computation Conference, GECCO-2010

作者： Johannsen, Daniel Kurur, Piyush P. Lengler, Johannes Max Planck Institute for Informatics Department of Algorithms and Complexity Saarbrücken Germany Dept. of Comp. Sei. and Engg. Indian Institute of Technology Kanpur Kanpur UP 208016 India Department of Mathematics Saarland University Saarbrücken Germany

ISBN: (纸本)9781450300728

In this article, we formulate for the first time the notion of a quantum evolutionary algorithm. In fact we define a quantum analogue for any elitist (1+1) randomized search heuristic. The quantum evolutionary algorithm, which we call (1+1) quantum evolutionary algorithm (QEA), is the quantum version of the classical (1+1) evolutionary algorithm (EA), and runs only on a quantum computer. It uses Grover search [13] to accelerate the search for improved offsprings. To understand the speedup of the (1+1) QEA over the (1+1) EA, we study the three well known pseudo-Boolean optimization problems ONEMAX, LEADINGONES, and DISCREPANCY. We show that although there is a speedup in the case of ONEMAX and LEADINGONES in the quantum setting, the speedup is less than quadratic. For DISCREPANCY, we show that the speedup is at best constant. The reason for this inconsistency is due to the difference in the probability of making a successful mutation. On the one hand, if the probability of making a successful mutation is large then quantum acceleration does not help much. On the other hand, if the probabilities of making a successful mutation is small then quantum enhancement indeed helps. Copyright 2010 ACM.

关键词： Evolutionary algorithms

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Galby, Esther Munaro, Andrea Yang, Shizhou Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Department of Mathematical Physical and Computer Sciences University of Parma Parma Italy School of Mathematics and Physics Queen's University Belfast Belfast United Kingdom

We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graph classes. Our approach unifies and extends several known polynomial-time approximation schemes on seemingly unrelated graph classes, such as classes of intersection graphs of fat objects in a fixed dimension or proper minor-closed classes. We also study the related notion of layered tree-independence number, a relaxation of layered treewidth. Copyright © 2023, The Authors. All rights reserved.

关键词： Polynomial approximation

Dense steiner problems: Approximation algorithms and inapproximability

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Karpinski, Marek Lewandowski, Mateusz Meesum, Syed Mohammad Mnich, Matthias Universität Bonn Institut für Informatik Bonn Germany University of Wrocaw Institute of Computer Science Wrocaw Poland Tu Hamburg Institute for Algorithms and Complexity Hamburg Germany

The Steiner Tree problem is a classical problem in com-binatorial optimization: the goal is to connect a set T of terminals in a graph G by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the δ-dense version of Steiner Tree, where each terminal has at least δ|V(G) \ T| neighbours outside T, for a fixed δ > 0. They gave a PTAS for this problem. We study a generalization of pairwise δ-dense Steiner Forest, which asks for a minimum-size forest in G in which the nodes in each terminal set T1,... ,Tkare connected, and every terminal in Tihas at least δ|Tj| neighbours in Tj, and at least δ|S| nodes in S = V(G) \ (T1∪ · · · ∪ Tk), for each i,j in {1,... , k} with i ≠ j. Our first result is a polynomial-time approximation scheme for all δ > 1/2. Then, we show a (13/12 + ϵ)-approximation algorithm for δ = 1/2 and any ϵ > 0. We also consider the δ-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is APX-hard. Copyright © 2020, The Authors. All rights reserved.

关键词： Approximation algorithms