TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Wed, 26 Jan 2022 10:47:14 GMT2022-01-26T10:47:14Z50281- Hitting long directed cycles is fixed-parameter tractablehttp://hdl.handle.net/11420/5756Title: Hitting long directed cycles is fixed-parameter tractable
Authors: Göke, Alexander; Marx, Dániel; Mnich, Matthias
Abstract: In the Directed Long Cycle Hitting Set problem we are given a directed graph G, and the task is to find a set S of at most k vertices/arcs such that G − S has no cycle of length longer than `. We show that the problem can be solved in time 2O(`6+`k3 log k+k5 log k log `) · nO(1), that is, it is fixed-parameter tractable (FPT) parameterized by k and `. This algorithm can be seen as a far-reaching generalization of the fixed-parameter tractability of Mixed Graph Feedback Vertex Set [Bonsma and Lokshtanov WADS 2011], which is already a common generalization of the fixed-parameter tractability of (undirected) Feedback Vertex Set and the Directed Feedback Vertex Set problems, two classic results in parameterized algorithms. The algorithm requires significant insights into the structure of graphs without directed cycles of length longer than and can be seen as an exact version of the approximation algorithm following from the Erdős-Pósa property for long cycles in directed graphs proved by Kreutzer and Kawarabayashi [STOC 2015]. © Alexander Göke, Dániel Marx, and Matthias Mnich; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/57562020-01-01T00:00:00Z
- Dense Steiner problems: approximation algorithms and inapproximabilityhttp://hdl.handle.net/11420/5996Title: Dense Steiner problems: approximation algorithms and inapproximability
Authors: Karpinski, Marek; Lewandowski, Mateusz; Meesum, Syed Mohammad; Mnich, Matthias
Abstract: The Steiner Tree problem is a classical problem in combinatorial 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 T₁,…,Tk are connected, and every terminal in Tᵢ has at least δ |Tⱼ| neighbours in Tⱼ, and at least δ|S| nodes in S = V(G)∖ (T₁∪…∪ 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.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/59962020-01-01T00:00:00Z
- A time- and space-optimal algorithm for the many-visits TSPhttp://hdl.handle.net/11420/4450Title: A time- and space-optimal algorithm for the many-visits TSP
Authors: Berger, André; Kozma, László; Mnich, Matthias; Vincze, Roland
Abstract: The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number k_c of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families.
The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time n^{O(n)} + O(n^3 \log \sum_c k_c ) and requires n^{O(n)} space. The interesting feature of the Cosmadakis-Papadimitriou algorithm is its \emph{logarithmic} dependence on the total length \sum_c k_c of the tour, allowing the algorithm to handle instances with very long tours, beyond what is tractable in the standard TSP setting. However, its superexponential dependence on the number of cities in both its time and space complexity renders the algorithm impractical for all but the narrowest range of this parameter.
In this paper we significantly improve on the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in
time 2^{O(n)}, i.e.\ single-exponential in the number of cities, with polynomial space. The space requirement of our algorithm is (essentially) the size of the output, and assuming the Exponential-time Hypothesis (ETH), the time requirement is optimal. Our algorithm is deterministic, and arguably both simpler and easier to analyse than the original approach of Cosmadakis and Papadimitriou. It involves an optimization over directed spanning trees and a recursive, centroid-based decomposition of trees.
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/44502019-01-01T00:00:00Z
- Single machine batch scheduling to minimize the weighted number of tardy jobshttp://hdl.handle.net/11420/3924Title: Single machine batch scheduling to minimize the weighted number of tardy jobs
Authors: Hermelin, Danny; Mnich, Matthias; Omlor, Simon
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/39242019-01-01T00:00:00Z
- A 3/2-approximation for the metric many-visits path TSPhttp://hdl.handle.net/11420/6891Title: A 3/2-approximation for the metric many-visits path TSP
Authors: Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
Abstract: In the Many-visits Path TSP, we are given a set of n cities along with their pairwise distances (or cost) c(uv), and moreover each city v comes with an associated positive integer request r(v). The goal is to find a minimum-cost path, starting at city s and ending at city t, that visits each city v exactly r(v) times.
We present a 3/2-approximation algorithm for the metric Many-visits Path TSP, that runs in time polynomial in n and poly-logarithmic in the requests r(v).
Our algorithm can be seen as a far-reaching generalization of the 3/2-approximation algorithm for Path TSP by Zenklusen (SODA 2019), which answered a long-standing open problem by providing an efficient algorithm which matches the approximation guarantee of Christofides' algorithm from 1976 for metric TSP.
One of the key components of our approach is a polynomial-time algorithm to compute a connected, degree bounded multigraph of minimum cost.
We tackle this problem by generalizing a fundamental result of Király, Lau and Singh (Combinatorica, 2012) on the Minimum Bounded Degree Matroid Basis problem, and devise such an algorithm for general polymatroids, even allowing element multiplicities.
Our result directly yields a 3/2-approximation to the metric Many-visits TSP, as well as a 3/2-approximation for the problem of scheduling classes of jobs with sequence-dependent setup times on a single machine so as to minimize the makespan.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/68912020-01-01T00:00:00Z
- Multitype integer monoid optimization and applicationshttp://hdl.handle.net/11420/5005Title: Multitype integer monoid optimization and applications
Authors: Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
Abstract: Configuration integer programs (IP) have been key in the design of algorithms for NP-hard
high-multiplicity problems since the pioneering work of Gilmore and Gomory [Oper. Res., 1961].
Configuration IPs have one variable for each possible configuration, which describes a placement
of items into a location, and whose value corresponds to the number of locations with that
placement. In high multiplicity problems items come in types, and are represented succinctly
by a vector of multiplicities; solving the configuration IP then amounts to deciding whether the
input vector of multiplicities of items of each type can be decomposed into a given number of
configurations.
We make this typically implicit notion explicit by observing that the set of all input vectors
which can be decomposed into configurations forms a monoid of configurations, and the problem
corresponding to solving the configuration IP is the Monoid Decomposition problem. Then,
motivated by applications, we enrich this problem in two ways. First, in certain problems each
configuration additionally has an objective value, and the problem becomes an optimization
problem of finding a “best” decomposition under the given objective. Second, there are often
different types of configurations derived from different types of locations. The resulting problem
is then to optimize over decompositions of the input multiplicity vector into configurations of
several types, and we call it Multitype Integer Monoid Optimization, or simply MIMO.
We develop fast exact (exponential-time) algorithms for various MIMO with few or many
location types and with various objectives. Our algorithms build on a novel proximity theorem
which connects the solutions of a certain configuration IP to those of its continuous relaxation.
We then cast several fundamental scheduling and bin packing problems as MIMOs, and thereby
obtain new or substantially faster algorithms for them.
We complement our positive algorithmic results by hardness results which show that, under
common complexity assumptions, the algorithms cannot be extended into more relaxed regimes.
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/50052019-01-01T00:00:00Z
- Degree-bounded generalized polymatroids and approximating the metric many-visits TSPhttp://hdl.handle.net/11420/5002Title: Degree-bounded generalized polymatroids and approximating the metric many-visits TSP
Authors: Bérczi, Kristóf; Berger, André; Mnich, Matthias; Vincze, Roland
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11420/50022019-01-01T00:00:00Z
- Scheduling with non-renewable resources: Minimizing the sum of completion timeshttp://hdl.handle.net/11420/7091Title: Scheduling with non-renewable resources: Minimizing the sum of completion times
Authors: Bérczi, Kristóf; Király, Tamás; Omlor, Simon
Abstract: We consider single-machine scheduling problems with a non-renewable resource. In this setting, there are n jobs, each characterized by a processing time, a weight, and a resource requirement. At given points in time, certain amounts of the resource are made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that each job has the required resource amount available at the start of its processing. We consider the objective of minimizing the weighted sum of completion times. The main contribution of the paper is a PTAS for the case of 0 processing times (formula presented). In addition, we show strong NP-hardness of the case of unit resource requirements and weights (formula presented), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the latter problem.
Fri, 01 May 2020 00:00:00 GMThttp://hdl.handle.net/11420/70912020-05-01T00:00:00Z
- On short fastest paths in temporal graphshttp://hdl.handle.net/11420/8390Title: On short fastest paths in temporal graphs
Authors: Danda, Umesh Sandeep; Ramakrishna, G.; Schmidt, Jens M.; Srikanth, M.
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/11420/83902021-01-01T00:00:00Z
- Reachability switching gameshttp://hdl.handle.net/11420/9156Title: Reachability switching games
Authors: Fearnley, John; Gairing, Martin; Mnich, Matthias; Savani, Rahul
Abstract: We study the problem of deciding the winner of reachability switching games for zero-, one-, and two-player variants. Switching games provide a deterministic analogue of stochastic games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. For the zero-player case, we also show P-hardness for a succinctly-represented model that maintains the upper bound of NP \ coNP. For the one- and two-player cases, our results hold in both the natural, explicit model and succinctly-represented model. Our results show that the switching variant of a game is harder in complexity-theoretic terms than the corresponding stochastic version.
Thu, 22 Apr 2021 00:00:00 GMThttp://hdl.handle.net/11420/91562021-04-22T00:00:00Z
- On the complexity of solving a decision problem with flow-depending costs: The case of the IJsselmeer dikeshttp://hdl.handle.net/11420/4602Title: On the complexity of solving a decision problem with flow-depending costs: The case of the IJsselmeer dikes
Authors: Abiad, Aida; Gribling, Sander; Lahaye, Domenico; Mnich, Matthias; Regts, Guus; Vena, Luis; Verweij, Gerard; Zwaneveld, Peter
Abstract: We consider a fundamental integer programming (IP) model for cost–benefit analysis and flood protection through dike building in the Netherlands, due to Zwaneveld and Verweij (2017). Experimental analysis with data for the IJsselmeer shows that the solution of the linear programming relaxation of the IP model is integral. This naturally leads to question whether the polytope associated to the IP is always integral. In this paper we first give a negative answer to this question by proving the non-integrality of the polytope. Secondly, we establish natural conditions that guarantee the linear programming relaxation of the IP model is integral. We show that these conditions are indeed satisfied by the recent data on flood probabilities, damage and investment costs of IJsselmeer. Finally, we show that the IP model can be solved in polynomial time when the number of dike segments, or the number of feasible barrier heights, are bounded.
Sat, 01 Aug 2020 00:00:00 GMThttp://hdl.handle.net/11420/46022020-08-01T00:00:00Z
- Time- and space-optimal algorithm for the many-visits TSPhttp://hdl.handle.net/11420/4732Title: Time- and space-optimal algorithm for the many-visits TSP
Authors: Berger, André; Kozma, László; Mnich, Matthias; Vincze, Roland
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/47322020-01-01T00:00:00Z
- Combinatorial n-fold integer programming and applicationshttp://hdl.handle.net/11420/4313Title: Combinatorial n-fold integer programming and applications
Authors: Knop, Dušan; Koutecký, Martin; Mnich, Matthias
Abstract: Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the size of the ILP. That algorithm became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra’s algorithm has two drawbacks: First, the run time of the resulting algorithms is often double-exponential in the parameter, and second, an ILP formulation in small dimension cannot easily express problems involving many different costs. Inspired by the work of Hemmecke et al. (Math Program 137(1–2, Ser. A):325–341, 2013), we develop a single-exponential algorithm for so-called combinatorialn-fold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to many relevant problems problems like Closest String, Swap Bribery, Weighted Set Multicover, and several others, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both. Unlike Lenstra’s algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial n-fold IPs, existence of an augmenting step implies existence of a “local” augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.
Fri, 01 Nov 2019 00:00:00 GMThttp://hdl.handle.net/11420/43132019-11-01T00:00:00Z
- Voting and bribing in single-exponential timehttp://hdl.handle.net/11420/5436Title: Voting and bribing in single-exponential time
Authors: Knop, Dušan; Koutecký, Martin; Mnich, Matthias
Abstract: We introduce a general problem about bribery in voting systems. In theR-Multi-Briberyproblem,the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the perturbedelection under the voting ruleR. Voters assign prices for withdrawing their vote, for swapping thepositions of two consecutive candidates in their preference order, and for perturbing their approval countto favour candidates.As our main result, we show thatR-Multi-Briberyis fixed-parameter tractable parameterized bythe number of candidates for many natural voting rulesR, including Kemeny rule, all scoring protocols,maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves theparameterized complexity ofR-Swap Briberyfor all those voting rules, thereby solving a long-standingopen problem and “Challenge #2” of the “Nine Research Challenges in Computational Social Choice”by Bredereck et al.Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlierdouble-exponential time algorithm by Dorn and Schlotter that is restricted to the uniform-cost case forall scoring protocols, the maximin rule, and Bucklin rule.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/54362020-01-01T00:00:00Z
- Dynamic parameterized problems and algorithmshttp://hdl.handle.net/11420/5772Title: Dynamic parameterized problems and algorithms
Authors: Alman, Josh; Mnich, Matthias; Vassilevska Williams, Virginia
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/57722020-01-01T00:00:00Z
- Solving packing problems with few small items using rainbow matchingshttp://hdl.handle.net/11420/6533Title: Solving packing problems with few small items using rainbow matchings
Authors: Bannach, Max; Berndt, Sebastian; Maack, Marten; Mnich, Matthias; Lassota, Alexandra; Rau, Malin; Skambath, Malte
Abstract: An important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been studied extensively from the viewpoint of approximation algorithms, but their parameterized complexity has only been investigated barely. For problem instances containing no “small” items, classical matching algorithms yield optimal solutions in polynomial time. In this paper we approach them by their distance from triviality, measuring the problem complexity by the number k of small items.
Our main results are fixed-parameter algorithms for vector versions of Bin Packing, Multiple Knapsack, and Bin Covering parameterized by k. The algorithms are randomized with one-sided error and run in time 4k · k! · nO(1). To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications. We also present a deterministic fixed-parameter algorithm for Bin Packing with run time O((k!)2 · k · 2k · n log(n)).
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/65332020-01-01T00:00:00Z
- Resolving infeasibility of linear systems: a parameterized approachhttp://hdl.handle.net/11420/4603Title: Resolving infeasibility of linear systems: a parameterized approach
Authors: Göke, Alexander; Mendoza Cadena, Lydia Mirabel; Mnich, Matthias
Abstract: Deciding feasibility of large systems of linear equations and inequalities is one of the most fundamental algorithmic tasks. However, due to inaccuracies of the data or modeling errors, in practical applications one often faces linear systems that are infeasible. Extensive theoretical and practical methods have been proposed for post-infeasibility analysis of linear systems. This generally amounts to detecting a feasibility blocker of small size k, which is a set of equations and inequalities whose removal or perturbation from the large system of size m yields a feasible system. This motivates a parameterized approach towards post-infeasibility analysis, where we aim to find a feasibility blocker of size at most k in fixed-parameter time f(k) · mO(1). On the one hand, we establish parameterized intractability (W[1]-hardness) results even in very restricted settings. On the other hand, we develop fixed-parameter algorithms parameterized by the number of perturbed inequalities and the number of positive/negative right-hand sides. Our algorithms capture the case of Directed Feedback Arc Set, a fundamental parameterized problem whose fixed-parameter tractability was shown by Chen et al. (STOC 2008).
Sun, 01 Dec 2019 00:00:00 GMThttp://hdl.handle.net/11420/46032019-12-01T00:00:00Z
- Engineering kernelization for maximum cuthttp://hdl.handle.net/11420/4696Title: Engineering kernelization for maximum cut
Authors: Ferizovic, Damir; Hespe, Damian; Lamm, Sebastian; Mnich, Matthias; Schulz, Christian; Strash, Darren
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/46962020-01-01T00:00:00Z
- Odd multiway cut in directed acyclic graphshttp://hdl.handle.net/11420/5836Title: Odd multiway cut in directed acyclic graphs
Authors: Chandrasekaran, Karthekeyan; Mnich, Matthias; Mozaffari, Sahand
Abstract: We investigate the odd multiway node (edge) cut problem where the input is a graph with a specified collection of terminal nodes and the goal is to find a smallest subset of nonterminal nodes (edges) to delete so that the terminal nodes do not have an odd length path between them. In an earlier work, Lokshtanov and Ramanujan showed that both odd multiway node cut and odd multiway edge cut are fixed-parameter tractable (FPT) when parameterized by the size of the solution in undirected graphs. In this work, we focus on directed acyclic graphs (DAGs) and design a fixed-parameter algorithm. Our main contribution is a broadening of the shadow-removal framework to address parity problems in DAGs. We complement our FPT results with tight approximability as well as polyhedral results for 2 terminals in DAGs. Additionally, we show inapproximability results for odd multiway edge cut in undirected graphs even for 2 terminals.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/58362020-01-01T00:00:00Z
- Stable matchings with covering constraints: a complete computational trichotomyhttp://hdl.handle.net/11420/4786Title: Stable matchings with covering constraints: a complete computational trichotomy
Authors: Mnich, Matthias; Schlotter, Ildikó
Abstract: Stable matching problems with lower quotas are fundamental in academic hiring andensuring operability of rural hospitals. Only few tractable (polynomial-time solvable)cases of stable matching with lower quotas have been identified; most such problemsareNP-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 arelaxed notion of tractability, namely fixed-parameter tractability. By cloning hospitalswe focus on the case when all hospitals have upper quota equal to 1, which general-izes the setting of “arranged marriages” first considered by Knuth (Mariages stableset leurs relations avec d’autres problèmes combinatoires, Les Presses de l’Universitéde Montréal, Montreal, 1976). We investigate how a set of natural parameters, namelythe maximum length of preference lists for men and women, the number of distin-guished men and women, and the number of blocking pairs allowed determine thecomputational tractability of this problem. Our main result is a complete complexitytrichotomy: for each choice of parameters we either provide a polynomial-time algo-rithm, or anNP-hardness proof and fixed-parameter algorithm, orNP-hardness proofandW[1]-hardness proof. As corollary, we negatively answer a question by Hamadaet al. (Algorithmica 74(1):440–465, 2016) by showing fixed-parameter intractabil-ity parameterized by optimal solution size. We also classify all cases of one-sidedconstraints where only women may be distinguished.
Thu, 06 Feb 2020 00:00:00 GMThttp://hdl.handle.net/11420/47862020-02-06T00:00:00Z
- Cycle spectra of contraction-critically 4-connected planar graphshttp://hdl.handle.net/11420/9863Title: Cycle spectra of contraction-critically 4-connected planar graphs
Authors: Lo, On-Hei Solomon; Schmidt, Jens M.
Abstract: Motivated by the long-standing and wide open pancyclicity conjectures of Bondy and Malkevitch, we study the cycle spectra of contraction-critically 4-connected planar graphs. We show that every contraction-critically 4-connected planar graph on n vertices contains a cycle of length k for every k∈⌊n2⌋-⌈n108⌉,⋯,⌊n2⌋+⌊n36⌋∪23n,⋯,n.
Tue, 29 Jun 2021 00:00:00 GMThttp://hdl.handle.net/11420/98632021-06-29T00:00:00Z
- Circumference of essentially 4-connected planar triangulationshttp://hdl.handle.net/11420/8419Title: Circumference of essentially 4-connected planar triangulations
Authors: Fabrici, Igor; Harant, Jochen; Mohr, Samuel; Schmidt, Jens M.
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/11420/84192021-01-01T00:00:00Z
- Approximating sparsest cut in low-treewidth graphs via combinatorial diameterhttp://hdl.handle.net/11420/10926Title: Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
Authors: Chalermsook, Parinya; Kaul, Matthias; Mnich, Matthias; Spoerhase, Joachim; Uniyal, Sumedha; Vaz, Daniel
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/11420/109262021-01-01T00:00:00Z
- Parameterized complexity of configuration integer programshttp://hdl.handle.net/11420/11096Title: Parameterized complexity of configuration integer programs
Authors: Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
Abstract: Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems. First, we develop fast exact (exponential-time) algorithms for Configuration IP and matching hardness results. Second, we showcase the implications of these results to bin-packing and facility-location-like problems.
©2021 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND
Mon, 15 Nov 2021 00:00:00 GMThttp://hdl.handle.net/11420/110962021-11-15T00:00:00Z
- Hitting weighted even cycles in planar graphshttp://hdl.handle.net/11420/9788Title: Hitting weighted even cycles in planar graphs
Authors: Göke, Alexander; Koenemann, Jochen; Mnich, Matthias; Sun, Hao
Abstract: A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family F. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTAS) for planar input graphs G, using a variety of techniques like the shifting technique (Baker, J. ACM 1994), bidimensionality (Fomin et al., SODA 2011), or connectivity domination (Cohen-Addad et al., STOC 2016). These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known.
In the even-cycle transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini et al. (IPCO 2010) showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10.
Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap of the same value for the standard LP relaxation on node-weighted planar graphs.
Wed, 15 Sep 2021 00:00:00 GMThttp://hdl.handle.net/11420/97882021-09-15T00:00:00Z
- Efficient approximations for many-visits multiple traveling salesman problemshttp://hdl.handle.net/11420/11435Title: Efficient approximations for many-visits multiple traveling salesman problems
Authors: Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
Abstract: A fundamental variant of the classical traveling salesman problem (TSP) is the so-called multiple TSP (mTSP), where a set of m salesmen jointly visit all cities from a set of n cities. The mTSP models many important real-life applications, in particular for vehicle routing problems. An extensive survey by Bektas (Omega 34(3), 2006) lists a variety of heuristic and exact solution procedures for the mTSP, which quickly solve particular problem instances.
In this work we consider a further generalization of mTSP, the many-visits mTSP, where each city v has a request r(v) of how many times it should be visited by the salesmen. This problem opens up new real-life applications such as aircraft sequencing, while at the same time it poses several computational challenges. We provide multiple efficient approximation algorithms for important variants of the many-visits mTSP, which are guaranteed to quickly compute high-quality solutions for all problem instances.
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/11420/114352021-01-01T00:00:00Z
- Recent advances in practical data reductionhttp://hdl.handle.net/11420/8301Title: Recent advances in practical data reduction
Authors: Abu-Khzam, Faisal; Lamm, Sebastian; Mnich, Matthias; Noe, Alexander; Schulz, Christian; Strash, Darren
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/83012020-01-01T00:00:00Z
- Optimizing fuel consumption on inland waterway networks : local search heuristic for lock schedulinghttp://hdl.handle.net/11420/11534Title: Optimizing fuel consumption on inland waterway networks : local search heuristic for lock scheduling
Authors: Golak, Julian; Defryn, Christof; Grigoriev, Alexander
Mon, 17 Jan 2022 00:00:00 GMThttp://hdl.handle.net/11420/115342022-01-17T00:00:00Z