Author name cluster

Matthias Mnich

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

IJCAI Conference 2024 Conference Paper

Efficient Cost-Minimization Schemes for Electrical Energy Demand Satisfaction by Prosumers in Microgrids with Battery Storage Capabilities

Laura Codazzi
Gergely Csáji
Matthias Mnich

We introduce and study various models for satisfying electrical energy demands of prosumers in a microgrid, while optimizing their costs. Each prosumer has individual demands of electrical energy, which can vary day-by-day, and which they can satisfy by either generating electrical energy through a self-operated mini power plant like a solar panel, through buying from an external energy provider, such as the main grid or by trading with other prosumers. Our models take into account two key aspects motivated by real-life scenarios: first, we consider a daily volatility of prices for buying and selling the energy, and second, the possibility to store the self-generated energy in a battery of finite capacity to be either self-consumed or sold to other prosumers in the future. We provide a thorough complexity analysis, as well as efficient algorithms, so that prosumers can minimize their overall cost over the entire time horizon. As a byproduct, we also solve a new, generalized version of the KNAPSACK problem which may be of independent interest. We complement our theoretical findings by extensive experimental evaluations on realistic data sets.

PDF Details DOI

FOCS Conference 2023 Conference Paper

Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding

Ariel Kulik
Matthias Mnich
Hadas Shachnai

We study the d-DIMENSIONAL VECTOR BIN PACKING ($d \mathbf{V B P})$ problem, a generalization of BIN PACKING with central applications in resource allocation and scheduling. In $d \mathrm{VBP}$, 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 d VBP that yields a ratio of $(1+\ln d-\chi(d)+\varepsilon)$ for all $d \in \mathbb{N}$ and any $\varepsilon\gt0$; here, $\chi(d)$ is some strictly positive function. This improves upon the best known asymptotic ratio of $(1+\ln d+\varepsilon)$ due to Bansal, Caprara and Sviridenko (SICOMP 2010) for any $d\gt3$. By slightly modifying our algorithm to include an initial matching phase and applying a tighter analysis, we obtain an asymptotic approximation ratio of $\left(\frac{4}{3}+\varepsilon\right)$ for the special case of $d=2$, thus substantially improving the previous best ratio of $\left(\frac{3}{2}+\varepsilon\right)$ 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 d VBP, leading to simple algorithms with improved approximation guarantees.

Details

MFCS Conference 2020 Conference Paper

Solving Packing Problems with Few Small Items Using Rainbow Matchings

Max Bannach
Sebastian Berndt 0001
Marten Maack
Matthias Mnich
Alexandra Lassota
Malin Rau
Malte Skambath

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 4^k⋅ k! ⋅ n^{O(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 Covering with run time O((k!)² ⋅ k ⋅ 2^k ⋅ n log(n)).

Details

SODA Conference 2019 Conference Paper

A time- and space-optimal algorithm for the many-visits TSP

André Berger
László Kozma 0002
Matthias Mnich
Roland Vincze

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 Σ c k c ) and requires n O ( n ) space. The interesting feature of the Cosmadakis-Papadimitriou algorithm is its logarithmic dependence on the total length Σ 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.

Details

AAMAS Conference 2018 Conference Paper

A Unifying Framework for Manipulation Problems

Du�an Knop
Martin Kouteck�
Matthias Mnich

Manipulation models for electoral systems are a core research theme in social choice theory; they include bribery (unweighted, weighted, swap, shift, .. .), control (by adding or deleting voters or candidates), lobbying in referenda and others. We develop a unifying framework for manipulation models with few types of people, one of the most commonly studied scenarios. A critical insight of our framework is to separate the descriptive complexity of the voting rule R from the number of types of people. This allows us to finally settle the computational complexity of R-Swap Bribery, one of the most fundamental manipulation problems. In particular, we prove that R-Swap Bribery is fixedparameter tractable when R is Dodgson’s rule and Young’s rule, when parameterized by the number of candidates. This way, we resolve a long-standing open question from 2007 which was explicitly asked by Faliszewski et al. [JAIR 40, 2011]. Our algorithms reveal that the true hardness of bribery problems often stems from the complexity of the voting rules. On one hand, we give a fixed-parameter algorithm parameterized by number of types of people for complex voting rules. Thus, we reveal that R-Swap Bribery with Dodgson’s rule is much harder than with Condorcet’s rule, which can be expressed by a conjunction of linear inequalities, while Dodson’s rule requires quantifier alternation and a bounded number of disjunctions of linear systems. On the other hand, we give an algorithm for quantifier-free voting rules which is parameterized only by the number of conjunctions of the voting rule and runs in time polynomial in the number of types of people. This way, our framework explains why Shift Bribery is polynomial-time solvable for the plurality voting rule, making explicit that the rule is simple in that it can be expressed with a single linear inequality, and that the number of voter types is polynomial.

PDF

IJCAI Conference 2015 Conference Paper

When Does Schwartz Conjecture Hold?

Matthias Mnich
Yash Raj Shrestha
Yongjie Yang

In 1990, Thomas Schwartz proposed the conjecture that every nonempty tournament has a unique minimal τ-retentive set (τ stands for tournament equilibrium set). A weak variant of Schwartz’s Conjecture was recently proposed by Felix Brandt. However, both conjectures were disproved very recently by two counterexamples. In this paper, we prove sufficient conditions for infinite classes of tournaments that satisfy Schwartz’s Conjecture and Brandt’s Conjecture. Moreover, we prove that τ can be calculated in polynomial time in several infinite classes of tournaments. Furthermore, our results reveal some structures that are forbidden in every counterexample to Schwartz’s Conjecture.

PDF Details

TCS Journal 2013 Journal Article

Kernel and fast algorithm for dense triplet inconsistency

Sylvain Guillemot
Matthias Mnich

We study the parameterized complexity of inferring supertrees from sets of rooted triplets, an important problem in phylogenetics. For a set L of labels and a dense set T of triplets distinctly leaf-labeled by 3-subsets of L, we seek a tree distinctly leaf-labeled by L and containing all but at most k triplets from T as homeomorphic subtree. Our results are the first polynomial kernel for this problem, with O ( k 2 ) labels, and a subexponential fixed-parameter algorithm running in time O ( ∣ L ∣ 4 ) + 2 O ( k 1 / 3 log k ).

Details DOI

TCS Journal 2011 Journal Article

A Linear Kernel for Planar Connected Dominating Set

Daniel Lokshtanov
Matthias Mnich
Saket Saurabh

We provide polynomial time data reduction rules for Connected Dominating Set on planar graphs and analyze these to obtain a linear kernel for the planar Connected Dominating Set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs.

Details DOI