2025-05-15 | | Total: 8
Maximizing a single submodular set function subject to a cardinality constraint is a well-studied and central topic in combinatorial optimization. However, finding a set that maximizes multiple functions at the same time is much less understood, even though it is a formulation which naturally occurs in robust maximization or problems with fairness considerations such as fair influence maximization or fair allocation. In this work, we consider the problem of maximizing the minimum over many submodular functions, which is known as multiobjective submodular maximization. All known polynomial-time approximation algorithms either obtain a weak approximation guarantee or rely on the evaluation of the multilinear extension. The latter is expensive to evaluate and renders such algorithms impractical. We bridge this gap and introduce the first scalable and practical algorithm that obtains the best-known approximation guarantee. We furthermore introduce a novel application fair centrality maximization and show how it can be addressed via multiobjective submodular maximization. In our experimental evaluation, we show that our algorithm outperforms known algorithms in terms of objective value and running time.
We propose a dynamic working set method (DWS) for the problem $\min_{\mathtt{x} \in \mathbb{R}^n} \frac{1}{2}\|\mathtt{Ax}-\mathtt{b}\|^2 + \eta\|\mathtt{x}\|_1$ that arises from compressed sensing. DWS manages the working set while iteratively calling a regression solver to generate progressively better solutions. Our experiments show that DWS is more efficient than other state-of-the-art software in the context of compressed sensing. Scale space such that $\|b\|=1$. Let $s$ be the number of non-zeros in the unknown signal. We prove that for any given $\varepsilon > 0$, DWS reaches a solution with an additive error $\varepsilon/\eta^2$ such that each call of the solver uses only $O(\frac{1}{\varepsilon}s\log s \log\frac{1}{\varepsilon})$ variables, and each intermediate solution has $O(\frac{1}{\varepsilon}s\log s\log\frac{1}{\varepsilon})$ non-zero coordinates.
Imagine yourself moving to another place, and therefore, you need to pack all of your belongings into moving boxes with some capacity. In the classical bin packing model, you would try to minimize the number of boxes, knowing the exact size of each item you want to pack. In the online bin packing problem, you need to start packing the first item into a box, without knowing what other stuff is upcoming. Both settings are somewhat unrealistic, as you are likely not willing to measure the exact size of all your belongings before packing the first item, but you are not completely clueless about what other stuff you have when you start packing. In this article, we introduce the online bin packing with estimates model, where you start packing with a rough idea about the upcoming item sizes in mind. In this model, an algorithm receives a size estimate for every item in the input list together with an accuracy factor $\delta$ in advance. Just as for regular online bin packing the items are then presented iteratively. The actual sizes of the items are allowed to deviate from the size estimate by a factor of $\delta$. Once the actual size of an item is revealed the algorithm has to make an irrevocable decision on the question where to place it. This is the first time online bin packing is studied under this model. This article has three main results: First, no algorithm can achieve a competitive ratio of less than $\frac{4}{3}$, even for an arbitrary small factor $\delta>0$. Second, we present an algorithm that is $1.5$-competitive for all $\delta \leq \frac{1}{35}$. Finally, we design a strategy that yields a competitive ratio of $\frac{4}{3}$ under the assumption that not more than two items can be placed in the same bin, which is best possible in this setting.
Steiner Tree Packing (STP) is a notoriously hard problem in classical complexity theory, which is of practical relevance to VLSI circuit design. Previous research has approached this problem by providing heuristic or approximate algorithms. In this paper, we show the first FPT algorithms for STP parameterized by structural parameters of the input graph. In particular, we show that STP is fixed-parameter tractable by the tree-cut width as well as the fracture number of the input graph. To achieve our results, we generalize techniques from Edge-Disjoint Paths (EDP) to Generalized Steiner Tree Packing (GSTP), which generalizes both STP and EDP. First, we derive the notion of the augmented graph for GSTP analogous to EDP. We then show that GSTP is FPT by (1) the tree-cut width of the augmented graph, (2) the fracture number of the augmented graph, (3) the slim tree-cut width of the input graph. The latter two results were previously known for EDP; our results generalize these to GSTP and improve the running time for the parameter fracture number. On the other hand, it was open whether EDP is FPT parameterized by the tree-cut width of the augmented graph, despite extensive research on the structural complexity of the problem. We settle this question affirmatively.
Cartesian tree pattern matching consists of finding all the factors of a text that have the same Cartesian tree than a given pattern. There already exist theoretical and practical solutions for the exact case. In this paper, we propose the first algorithms for solving approximate Cartesian tree pattern matching with one difference given a pattern of length m and a text of length n. We present a generic algorithm that find all the factors of the text that have the same Cartesian tree of the pattern with one difference, using different notions of differences. We show that this algorithm has a O(nM) worst-case complexity and that, for several random models, the algorithm has a linear average-case complexity. We also present an automaton based algorithm, adapting [PALP19], that can be generalized to deal with more than one difference.
We consider the Euclidean bi-chromatic matching problem in the dynamic setting, where the goal is to efficiently process point insertions and deletions while maintaining a high-quality solution. Computing the minimum cost bi-chromatic matching is one of the core problems in geometric optimization that has found many applications, most notably in estimating Wasserstein distance between two distributions. In this work, we present the first fully dynamic algorithm for Euclidean bi-chromatic matching with sub-linear update time. For any fixed $\varepsilon > 0$, our algorithm achieves $O(1/\varepsilon)$-approximation and handles updates in $O(n^{\varepsilon})$ time. Our experiments show that our algorithm enables effective monitoring of the distributional drift in the Wasserstein distance on real and synthetic data sets, while outperforming the runtime of baseline approximations by orders of magnitudes.
For two d-dimensional point sets A, B of size up to n, the Chamfer distance from A to B is defined as CH(A,B) = \sum_{a \in A} \min_{b \in B} \|a-b\|. The Chamfer distance is a widely used measure for quantifying dissimilarity between sets of points, used in many machine learning and computer vision applications. A recent work of Bakshi et al, NeuriPS'23, gave the first near-linear time (1+eps)-approximate algorithm, with a running time of O(ndlog(n)/eps^2). In this paper we improve the running time further, to O(nd(loglog(n)+log(1/eps))/eps^2). When eps is a constant, this reduces the gap between the upper bound and the trivial Omega(dn) lower bound significantly, from O(log n) to O(loglog n).
Given a proper (list) colouring of a graph $G$, a recolouring step changes the colour at a single vertex to another colour (in its list) that is currently unused on its neighbours, hence maintaining a proper colouring. Suppose that each vertex $v$ has its own private list $L(v)$ of allowed colours such that $|L(v)|\ge \mbox{deg}(v)+1$. We prove that if $G$ is connected and its maximum degree $\Delta$ is at least $3$, then for any two proper $L$-colourings in which at least one vertex can be recoloured, one can be transformed to the other by a sequence of $O(|V(G)|^2)$ recolouring steps. We also show that reducing the list-size of a single vertex $w$ to $\mbox{deg}(w)$ can lead to situations where the space of proper $L$-colourings is `shattered'. Our results can be interpreted as showing a sharp phase transition in the Glauber dynamics of proper $L$-colourings of graphs. This constitutes a `local' strengthening and generalisation of a result of Feghali, Johnson, and Paulusma, which considered the situation where the lists are all identical to $\{1,\ldots,\Delta+1\}$.