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

High-multiplicity N-fold IP via configuration LP

MATHEMATICAL PROGRAMMING 2023年第1期200卷 199-227页

作者： Knop, Dusan Koutecky, Martin Levin, Asaf Mnich, Matthias Onn, Shmuel Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Prague Czech Republic Charles Univ Prague Fac Math & Phys Comp Sci Inst Prague Czech Republic Technion Israel Inst Technol Haifa Israel Hamburg Univ Technol Inst Algorithms & Complex Hamburg Germany

N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicityN-fold IPs, which encode IPs succinctly by presenting a description of each block type and a vector of block multiplicities. Our goal is to design algorithms which solve N-fold IPs in time polynomial in the size of the succinct encoding, which may be significantly smaller than the size of the explicit (non-succinct) instance. We present the first fixed-parameter algorithm for high-multiplicity N-fold IPs, which even works for convex objectives. Our key contribution is a novel proximity theorem which relates fractional and integer optima of the Configuration LP, a fundamental notion by Gilmore and Gomory [Oper. Res., 1961] which we generalize. Our algorithm for N-fold IP is faster than previous algorithms whenever the number of blocks is much larger than the number of block types, such as in N-fold IP models for various scheduling problems.

关键词： Integer programming Configuration IP fixed-parameter algorithms Scheduling

来源：评论

学校读者我要写书评

暂无评论

The parameterized Complexity of Stabbing Rectangles

引用

ALGORITHMICA 2012年第1-2期62卷 564-594页

作者： Dom, Michael Fellows, Michael R. Rosamond, Frances A. Sikdar, Somnath Rhein Westfal TH Aachen Dept Comp Sci D-52074 Aachen Germany Univ Jena Inst Informat D-07743 Jena Germany Charles Darwin Univ Sch Engn & Informat Technol Darwin NT 0909 Australia

The NP-complete geometric covering problem Rectangle Stabbing is defined as follows: Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines in the plane, and a positive integer k, select at most k of the lines such that every rectangle is intersected by at least one of the selected lines. While it is known that the problem can be approximated in polynomial time within a factor of two, its parameterized complexity with respect to the parameter k was open so far. Giving two fixed-parameter reductions, one from the W[1]-complete problem Multicolored Clique and one to the W[1]-complete problem Short Turing Machine Acceptance, we prove that Rectangle Stabbing is W[1]-complete with respect to the parameter k, which in particular means that there is no hope for an algorithm running in f(k)a <...|(RaL)-L-a| (O(1)) time. Our reductions also show the W[1]-completeness of the more general problem Set Cover on instances that "almost have the consecutive-ones property", that is, on instances whose matrix representation has at most two blocks of 1s per row. We also show that the special case of Rectangle Stabbing where all rectangles are squares of the same size is W[1]-hard. The case where the input consists of non-overlapping rectangles was open for some time and has recently been shown to be fixed-parameter tractable (Heggernes et al., fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009). By giving an algorithm running in (2k) (k) a <...|(RaL)-L-a| (O(1)) time, we show that Rectangle Stabbing is fixed-parameter tractable in the still NP-hard case where both these restrictions apply, that is, in the case of disjoint squares of the same size. This algorithm is faster than the one in Heggernes et al. (fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009) for the disjoint rectangles case. Moreover, we show fixed-parameter tractability for the restrictions where the rect

关键词： parameterized complexity fixed-parameter algorithms Geometric covering problems Whardness

来源：评论

学校读者我要写书评

暂无评论

Solving Problems on Graphs of High Rank-Width

引用

ALGORITHMICA 2018年第2期80卷 742-771页

作者： Eiben, Eduard Ganian, Robert Szeider, Stefan TU Wien Algorithms & Complex Grp Vienna Austria

A modulator in a graph is a vertex set whose deletion places the considered graph into some specified graph class. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited to obtain fixed-parameter algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Can such modulators still be exploited to obtain efficient algorithms? And is it even possible to find such modulators efficiently? We first show that the parameters derived from such well-structured modulators are more powerful for fixed-parameter algorithms than the cardinality of modulators and rank-width itself. Then, we develop a fixed-parameter algorithm for finding such well-structured modulators to every graph class which can be characterized by a finite set of forbidden induced subgraphs. We proceed by showing how well-structured modulators can be used to obtain efficient parameterized algorithms for Minimum Vertex Cover and Maximum Clique. Finally, we use the concept of well-structured modulators to develop an algorithmic meta-theorem for deciding problems expressible in monadic second order logic, and prove that this result is tight in the sense that it cannot be generalized to LinEMSO problems.

关键词： fixed-parameter algorithms Rank-width Monadic second-order logic parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Stable Matchings with Covering Constraints: A Complete Computational Trichotomy

引用

ALGORITHMICA 2020年第5期82卷 1136-1188页

作者： Mnich, Matthias Schlotter, Ildiko Univ Bonn Bonn Germany TU Hamburg Inst Algorithms & Complex Hamburg Germany Budapest Univ Technol & Econ Budapest Hungary

Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified;most such problems are NP-hard and also hard to approximate (Hamada et al. in Algorithmica 74(1):440-465, 2016). We therefore consider stable matching problems with lower quotas under a relaxed notion of tractability, namely fixed-parameter tractability. By cloning hospitals we focus on the case when all hospitals have upper quota equal to 1, which generalizes the setting of "arranged marriages" first considered by Knuth (Mariages stables et leurs relations avec d'autres problemes combinatoires, Les Presses de l'Universite de Montreal, Montreal, 1976). We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. Our main result is a complete complexity trichotomy: for each choice of parameters we either provide a polynomial-time algorithm, or an NP-hardness proof and fixed-parameter algorithm, or NP-hardness proof and W[1]-hardness proof. As corollary, we negatively answer a question by Hamada et al. (Algorithmica 74(1):440-465, 2016) by showing fixed-parameter intractability parameterized by optimal solution size. We also classify all cases of one-sided constraints where only women may be distinguished.

关键词： Stable marriage Lower quotas fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

New deterministic algorithms for solving parity games

引用

DISCRETE OPTIMIZATION 2018年 30卷 73-95页

作者： Mnich, Matthias Roeglin, Heiko Roesner, Clemens Univ Bonn Dept Comp Sci Bonn Germany Maastricht Univ Dept Quantitat Econ Maastricht Netherlands

We study parity games in which one of the two players controls only a small number k of nodes and the other player controls the n - k other nodes of the game. Our main result is a fixed-parameter algorithm that solves bipartite Parity games in time k(O(root k)) . O(n(3)), and general parity games in time (p + k)(O(root k)) . O(pnm), where p is the number of distinct priorities and m is the number of edges. For all games with k = o(n) this improves the previously fastest algorithm by Jurdzinski, Paterson, and Zwick (SICOMP 2008). We also obtain novel kernelization results and an improved deterministic algorithm for graphs with small average degree. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Parity games fixed-parameter algorithms Kernelization Subexponential algorithms

来源：评论

学校读者我要写书评

暂无评论

DETERMINISTIC algorithms FOR MATCHING AND PACKING PROBLEMS BASED ON REPRESENTATIVE SETS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第4期29卷 1815-1836页

作者： Goyal, Prachi Misra, Neeldhara Panolan, Fahad Zehavi, Meirav Indian Inst Sci Bangalore 560012 Karnataka India Inst Math Sci Madras 600113 Tamil Nadu India Technion Israel Inst Technol Haifa Israel

In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-SET k-PACKING ((r, k)-SP) problems. Given a universe U := U-1 ... U-r and an r-uniform family F subset of U-1 x ... x U-r, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F subset of 2(U), the (r, k)-SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851((r-1)k) .vertical bar F vertical bar. n log(2)n . logW) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851((r-0.5501)k).vertical bar F vertical bar.n log(2) n . logW) for the weighted version of (r, k)-SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)-SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3, k)-DM, running in time O(2.004(3k).vertical bar F vertical bar . n log(2)n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(e(r)r(k-1)(r) logW) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k-1)(r) logW) for these problems.

关键词： r-dimensional matching set packing 3D-matching fixed-parameter algorithms representative sets iterative expansion

来源：评论

学校读者我要写书评

暂无评论

An improved kernelization algorithm for r-Set Packing

引用

INFORMATION PROCESSING LETTERS 2010年第16期110卷 621-624页

作者： Abu-Khzam, Faisal N. Lebanese Amer Univ Dept Comp Sci & Math New York NY 10115 USA

We present a reduction procedure that takes an arbitrary instance of the r-Set Packing problem and produces an equivalent instance whose number of elements is in O(k(r-1)), where k is the input parameter. Such parameterized reductions are known as kernelization algorithms, and a reduced instance is called a problem kernel. Our result improves on previously known kernelizations by a factor of k. In particular, the number of elements in a 3-Set Packing kernel is improved from a cubic function of the parameter to a quadratic one. (C) 2010 Elsevier B.V. All rights reserved.

关键词： fixed-parameter algorithms Kernelization Crown decomposition Set Packing Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms and complexity results for power domination in graphs

引用

ALGORITHMICA 2008年第2期52卷 177-202页

作者： Guo, Jiong Niedermeier, Rolf Raible, Daniel Univ Jena Inst Informat D-07743 Jena Germany Univ Trier Abt Informat Wirtschaftsinformat Fachbereich 4 D-54286 Trier Germany

The NP-complete POWER DOMINATING SET problem is an "electric power networks variant" of the classical domination problem in graphs: Given an undirected graph G = (V, E), find a minimum-size set P. V such that all vertices in V are "observed" by the vertices in P. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. We show that POWER DOMINATING SET can be solved by "bounded-treewidth dynamic programs." For treewidth being upper-bounded by a constant, we achieve a linear-time algorithm. In particular, we present a simplified linear-time algorithm for POWER DOMINATING SET in trees. Moreover, we simplify and extend several NP-completeness results, particularly showing that POWER DOMINATING SET remains NP-complete for planar graphs, for circle graphs, and for split graphs. Specifically, our improved reductions imply that POWER DOMINATING SET parameterized by vertical bar P vertical bar is W[2]-hard and it cannot be better approximated than DOMINATING SET.

关键词： design and analysis of algorithms computational complexity parameterized complexity fixed-parameter algorithms graph algorithms graphs of bounded treewidth (power) domination in graphs

来源：评论

学校读者我要写书评

暂无评论

Comparing incomplete sequences via longest common subsequence

引用

THEORETICAL COMPUTER SCIENCE 2019年 796卷 272-285页

作者： Castelli, Mauro Dondi, Riccardo Mauri, Giancarlo Zoppis, Italo Univ Nova Lisboa NOVA Informat Management Sch NOVA IMS Campus Campolide P-1070312 Lisbon Portugal Univ Bergamo Dipartimento Sci Umane & Sociali Bergamo Italy Univ Milano Bicocca Dipartimento Informat Sistemist & Comunicaz Milan Italy

Inspired by scaffold filling, a recent approach for genome reconstruction from incomplete data, we consider a variant of the well-known longest common subsequence problem for the comparison of two sequences. The new problem, called Longest Filled Common Subsequence, aims to compare a complete sequence with an incomplete one, i.e. with some missing elements. Longest Filled Common Subsequence (LFCS), given a complete sequence A, an incomplete sequence B, and a multiset M of symbols missing in B, asks for a sequence B* obtained by inserting the symbols of M into B so that B* induces a common subsequence with A of maximum length. We investigate the computational and approximation complexity of the problem and we show that it is NP-hard and APX-hard when A contains at most two occurrences of each symbol, and we give a polynomial time algorithm when the input sequences are over a constant-size alphabet. We give a 3/5-approximation algorithm for the Longest Filled Common Subsequence problem. Finally, we present a fixed-parameter algorithm for the problem, when it is parameterized by the number of symbols inserted in B that "match" symbols of A. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Longest common subsequence String algorithms Approximation algorithms Computational complexity fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Influence of tree topology restrictions on the complexity of haplotyping with missing data

引用

THEORETICAL COMPUTER SCIENCE 2012年 432卷 38-51页

作者： Elberfeld, Michael Schnoor, Ilka Tantau, Till Med Univ Lubeck Inst Theoret Informat D-23538 Lubeck Germany Univ Kiel Inst Informat D-24118 Kiel Germany

Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast haplotyping method is based on an evolutionary model in which a perfect phylogenetic tree is sought that explains the observed data. Unfortunately, when data entries are missing, which is often the case in laboratory data, the resulting formal problem IPPH, which stands for incomplete perfect phylogeny haplotyping, is NP-complete. Even radically simplified versions, such as the restriction to phylogenetic trees consisting of just two directed paths from a given root, are still NP-complete;but here, at least, a fixed-parameter algorithm is known. Such drastic and ad hoc simplifications turn out to be unnecessary to make IPPH tractable: we present the first theoretical analysis of a parameterized algorithm, which we develop in the course of the paper, that works for arbitrary instances of IPPH. This tractability result is optimal insofar as we prove IPPH to be NP-complete whenever any of the parameters we consider is not fixed, but part of the input. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Computational biology Computational complexity fixed-parameter algorithms Haplotyping Phylogenies

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：