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

The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5 51

学校读者我要写书评

暂无评论

The k-Opt Algorithm for the Traveling Salesman Problem Has E...

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

作者： Heimann, Sophia Hoang, Hung P. Hougardy, Stefan Research Institute for Discrete Mathematics University of Bonn Germany Algorithms and Complexity Group Faculty of Informatics TU Wien Austria Research Institute for Discrete Mathematics and Hausdorff Center for Mathematics University of Bonn Germany

ISBN: (纸本)9783959773225

The k-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most k edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the k-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the k-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires k 1000 and has a substantial gap. We show the two properties above for a much smaller value of k, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for k ≥ 17 and the exponential running time for k ≥ 5. © Sophia Heimann, Hung P. Hoang, and Stefan Hougardy.

关键词： Traveling salesman problem

A Structural Complexity Analysis of Hierarchical Task Network Planning

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Brand, Cornelius Ganian, Robert Inerney, Fion Mc Wietheger, Simon Algorithms & Complexity Theory Group Regensburg University Germany Algorithms and Complexity Group TU Wien Austria Telefónica Scientific Research Barcelona Spain

We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an executable plan exists, and whether a given state can be reached. Our focus lies on identifying structural properties which yield tractability. We obtain new polynomial algorithms for all three problems on a natural class of primitive networks, along with corresponding lower bounds. We also obtain an algorithmic meta-theorem for lifting polynomial-time solvability from primitive to general task networks, and prove that its preconditions are tight. Finally, we analyze the parameterized complexity of the three problems. Copyright © 2024, The Authors. All rights reserved.

关键词： Complex networks

Problems on group-Labeled Matroid Bases 51

学校读者我要写书评

暂无评论

Problems on Group-Labeled Matroid Bases

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

作者： Hörsch, Florian Imolay, András Mizutani, Ryuhei Oki, Taihei Schwarcz, Tamás Algorithms and Complexity Group CISPA Saarbrücken Germany MTA-ELTE Matroid Optimization Research Group Department of Operations Research ELTE Eötvös Loránd University Budapest Hungary Department of Mathematical Informatics Graduate School of Information Science and Technology The University of Tokyo Japan

ISBN: (纸本)9783959773225

Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a matroid is not difficult, it turns out that the complexity of finding a non-zero common basis depends on the group. Namely, we show that the problem is hard for a fixed group if it contains an element of order two, otherwise it is polynomially solvable. As a generalization of both zero and non-zero constraints, we further study F-avoiding constraints where we seek a basis or common basis whose label is not in a given set F of forbidden labels. Using algebraic techniques, we give a randomized algorithm for finding an F-avoiding common basis of two matroids represented over the same field for finite groups given as operation tables. The study of F-avoiding bases with groups given as oracles leads to a conjecture stating that whenever an F-avoiding basis exists, an F-avoiding basis can be obtained from an arbitrary basis by exchanging at most |F| elements. We prove the conjecture for the special cases when |F| ≤ 2 or the group is ordered. By relying on structural observations on matroids representable over fixed, finite fields, we verify a relaxed version of the conjecture for these matroids. As a consequence, we obtain a polynomial-time algorithm in these special cases for finding an F-avoiding basis when |F| is fixed. © Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz.

关键词： Polynomial approximation

The Computational Complexity of Positive Non-Clashing Teaching in Graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Ganian, Robert Khazaliya, Liana Inerney, Fionn Mc Rocton, Mathis Algorithms and Complexity Group TU Wien Austria Telefónica Scientific Research Barcelona Spain

We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per concept required to successfully teach an intelligent learner under the considered, previously established model. For any class of concepts, it is known that this problem can be effortlessly transferred to the setting of balls in a graph G. We establish (1) the NP-hardness of the problem even when restricted to instances with positive non-clashing teaching dimension k = 2 and where all balls in the graph are present, (2) near-tight running time upper and lower bounds for the problem on general graphs, (3) fixed-parameter tractability when parameterized by the vertex integrity of G, and (4) a lower bound excluding fixed-parameter tractability when parameterized by the feedback vertex number and pathwidth of G, even when combined with k. Our results provide a nearly complete understanding of the complexity landscape of computing the positive non-clashing teaching dimension and answer open questions from the literature. Copyright © 2025, The Authors. All rights reserved.

关键词： Graph theory

Self-organizing Migrating Algorithm (SOMA) for Pumped-Storage Hydrothermal System Scheduling

学校读者我要写书评

暂无评论

Self-organizing Migrating Algorithm (SOMA) for Pumped-Storag...

International Conference on Advanced Engineering Theory and Applications, AETA 2022

作者： Phan, Tan Minh Trong Dao, Tran Power System Optimization Research Group Faculty of Electrical and Electronics Engineering Ton Duc Thang University Ho Chi Minh City Viet Nam Modeling Evolutionary Algorithms Simulation and Artificial Intelligence Research Group Faculty of Electrical and Electronics Engineering Ton Duc Thang University Ho Chi Minh City Viet Nam

ISBN: (纸本)9789819987023

This paper presents the results of one power system working over one day by running three algorithms, including Dragonfly algorithm (DA), Salp Swarm Algorithm (SSA) and the self-organizing migrating algorithm (SOMA). The power system is optimally operated by determining status Pump and status Generation together with the power outputs as the status Generation is selected. The cost of one thermal power plant is used as an objective function to evaluate the three applied algorithms. On the other hand, almost all constraints are from one pumped-storage hydro plant, and valid solutions must satisfy these considered constraints. As a result, SOMA is the best method with the lowest cost and the best stability. So, SOMA is an effective method, and pumped-storage hydro plant is very useful for generation. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.

关键词： Hydroelectric power plants

Parameterized Complexity of Caching in Networks*

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ganian, Robert Inerney, Fionn Mc Tsigkari, Dimitra Algorithms and Complexity Group TU Wien Vienna Austria Telefónica Scientific Research Barcelona Spain

The fundamental caching problem in networks asks to find an allocation of contents to a network of caches with the aim of maximizing the cache hit rate. Despite the problem's importance to a variety of research areas-including not only content delivery, but also edge intelligence and inference-and the extensive body of work on empirical aspects of caching, very little is known about the exact boundaries of tractability for the problem beyond its general NPhardness. We close this gap by performing a comprehensive complexity-theoretic analysis of the problem through the lens of the parameterized complexity paradigm, which is designed to provide more precise statements regarding algorithmic tractability than classical complexity. Our results include algorithmic lower and upper bounds which together establish the conditions under which the caching problem becomes tractable. Copyright © 2024, The Authors. All rights reserved.

关键词： Complex networks

An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling

学校读者我要写书评

暂无评论

ACM Journal of Experimental Algorithmics 2022年第1期27卷 1-36页

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal Bypass Road Bhauri Madhya Pradesh Bhopal462066 India TU Wien Algorithms and Complexity Group Favoritenstraße 9-11 Vienna1040 Austria

Map labeling is a classical problem in cartography and geographic information systems that asks to place labels for area, line, and point features, with the goal to select and place the maximum number of independent (i.e., overlap-free) labels. A practically interesting case is point labeling with axis-parallel rectangular labels of common size. In a fully dynamic setting, at each timestep, either a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum cardinality subset of pairwise independent labels with sublinear update time. Motivated by this, we study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on fully dynamic (insertion/deletion model) sets of axis-parallel rectangles of two types: (i) uniform height and width and (ii) uniform height and arbitrary width;both settings can be modeled as rectangle intersection graphs. We present the first deterministic algorithm for maintaining an MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with polylogarithmic update time. This breaks the natural barrier of update time (where is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4-approximate Max-IS with update time. In a subsequent algorithm, we establish the trade-off between approximation quality and update time , for . We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of unit-height and arbitrary-width rectangles with update time, where is the maximum size of an independent set of rectangles stabbed by any horizontal line. We implement our algorithms and report the results of an experimental comparison exploring the trade-off between solution quality and update time for synthetic and real-world map labeling instances. We

关键词： Approximation algorithms

An Improved Lower Bound on the Number of Pseudoline Arrangements

学校读者我要写书评

暂无评论

arXiv 2024年

Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years ago. The study of the number Bn of non-isomorphic simple arrangements of n pseudolines goes back to Goodman and Pollack, Knuth, and others. It is known that Bn is in the order of 2Θ(n2) and finding asymptotic bounds on bn = log2n(Bn)/n2 remains a challenging task. In 2011, Felsner and Valtr showed that 0.1887 ≤ bn ≤ 0.6571 for sufficiently large n. The upper bound remains untouched but in 2020 Dumitrescu and Mandal improved the lower bound constant to 0.2083. Their approach utilizes the known values of Bn for up to n = 12. We tackle the lower bound by utilizing dynamic programming and the Lindström–Gessel–Viennot lemma. Our new bound is bn ≥ 0.2721 for sufficiently large n. The result is based on a delicate interplay of theoretical ideas and computer assistance. Copyright © 2024, The Authors. All rights reserved.

关键词： Dynamic programming

LLMs as information warriors? Auditing how LLM-powered chatbots tackle disinformation about Russia’s war in Ukraine

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Makhortykh, Mykola Baghumyan, Ani Vziatysheva, Victoria Sydorova, Maryna Kuznetsova, Elizaveta Institute of Communication and Media Studies University of Bern Switzerland Research Group Platform Algorithms and Digital Propaganda Weizenbaum Institute Germany

The rise of large language models (LLMs) has a significant impact on information warfare. By facilitating the production of content related to disinformation and propaganda campaigns, LLMs can amplify different types of information operations and mislead online users. In our study, we empirically investigate how LLM-powered chatbots, developed by Google, Microsoft, and Perplexity, handle disinformation about Russia’s war in Ukraine and whether the chatbots’ ability to provide accurate information on the topic varies across languages and over time. Our findings indicate that while for some chatbots (Perplexity), there is a significant improvement in performance over time in several languages, for others (Gemini), the performance improves only in English but deteriorates in low-resource languages. © 2024, CC BY.

关键词： Economic and social effects