Similar Journals
|
Algorithmica
Journal Prestige (SJR): 0.56  Citation Impact (citeScore): 1 Number of Followers: 9  Hybrid journal (It can contain Open Access articles)ISSN (Print) 1432-0541 - ISSN (Online) 0178-4617 Published by Springer-Verlag  [2468 journals]
|
- Runtime Analysis with Variable Cost
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: The usual approach in runtime analysis is to derive estimates on the number of fitness function evaluations required by a method until a suitable element of the search space is found. One justification for this is that in real applications, fitness evaluation often contributes the most computational effort. A tacit assumption in this approach is that this effort is uniform and static across the search space. However, this assumption often does not hold in practice: some candidates may be far more expensive to evaluate than others. This might occur, for example, when fitness evaluation requires running a simulation or training a machine learning model. Despite the availability of a wide range of benchmark functions coupled with various runtime performance guarantees, the runtime analysis community currently lacks a solid perspective of handling variable fitness cost. Our goal with this paper is to argue for incorporating this perspective into our theoretical toolbox. We introduce two models of handling variable cost: a simple non-adaptive model together with a more general adaptive model. We prove cost bounds in these scenarios and discuss the implications for taking into account costly regions in the search space.
PubDate: 2025-04-18
-
- The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper, we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio $$A$$ have spanning ratio at most $$\sqrt{2} \sqrt{1+A^2 + A\sqrt{A^2 + 1}}$$, which matches the known lower bound.
PubDate: 2025-04-16
-
- Reconfiguration of the Union of Arborescences
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: An arborescence in a digraph is an acyclic arc subset in which every vertex except a root has exactly one incoming arc. In this paper, we show the reconfigurability of the union of k arborescences for fixed k in the following sense: for any pair of arc subsets that can be partitioned into k arborescences, one can be transformed into the other by exchanging arcs one by one so that every intermediate arc subset can also be partitioned into k arborescences. This generalizes the result by Ito et al. (2023), who showed the case with $$k=1$$. Since the union of k arborescences can be represented as a common matroid basis of two matroids, our result gives a new non-trivial example of matroid pairs for which two common bases are always reconfigurable to each other.
PubDate: 2025-04-11
-
- Improved Smoothed Analysis of 2-Opt for the Euclidean TSP
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: The 2-opt heuristic is a simple local search heuristic for the travelling salesperson problem (TSP). Although it usually performs well in practice, its worst-case running time is exponential in the number of cities. Attempts to reconcile this difference between practice and theory have used smoothed analysis, in which adversarial instances are perturbed probabilistically. We are interested in the classical model of smoothed analysis for the Euclidean TSP, in which the perturbations are Gaussian. This model was previously used by Manthey and Veenstra, who obtained smoothed complexity bounds polynomial in n, the dimension d, and the perturbation strength $$\sigma ^{-1}$$. However, their analysis only works for $$d \ge 4$$. The only previous analysis for $$d \le 3$$ was performed by Englert, Röglin and Vöcking, who used a different perturbation model which can be translated to Gaussian perturbations. Their model yields bounds polynomial in n and $$\sigma ^{-d}$$, and super-exponential in d. As the fact that no direct analysis exists for Gaussian perturbations that yields polynomial bounds for all d is somewhat unsatisfactory, we perform this missing analysis. Along the way, we improve all existing smoothed complexity bounds for Euclidean 2-opt with Gaussian perturbations.
PubDate: 2025-04-10
-
- Linear-Time MaxCut in Multigraphs Parameterized Above the
Poljak-Turzík Bound-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: MaxCut is a classical $$\textsf{NP}$$-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdös bound states that any connected graph on n vertices with m edges contains a cut of size at least $$\frac{m}{2}+\frac{n-1}{4}$$. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdös bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., $$f(k)\cdot O(m)$$. We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdös bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of weight at least $$\frac{w(G)}{2}+\frac{w_{MSF}(G)}{4}$$, where w(G) denotes the total weight of G, and $$w_{MSF}(G)$$ denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., $$f(k)\cdot O(m+n)$$.
PubDate: 2025-04-10
-
- Upward Pointset Embeddings of Planar st-Graphs
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We study upward pointset embeddings (UPSEs) of planar st-graphs. Let G be a planar st-graph and let $$S \subset \mathbb {R}^2$$ be a pointset with $$ S = V(G) $$. An UPSE of G on S is an upward planar straight-line drawing of G that maps the vertices of G to the points of S. We consider both the problem of testing the existence of an UPSE of G on S (UPSE Testing) and the problem of enumerating all UPSEs of G on S. We prove that UPSE Testing is NP-complete even for st-graphs that consist of a set of directed st-paths sharing only s and t. On the other hand, if G is an n-vertex planar st-graph whose maximum st-cutset has size k, then UPSE Testing can be solved in $$\mathcal {O}(n^{4k})$$ time with $$\mathcal {O}(n^{3k})$$ space; also, all the UPSEs of G on S can be enumerated with $$\mathcal {O}(n)$$ worst-case delay, using $$\mathcal {O}(k n^{4k} \log n)$$ space, after $$\mathcal {O}(k n^{4k} \log n)$$ set-up time. Moreover, for an n-vertex st-graph whose underlying graph is a cycle, we provide a necessary and sufficient condition for the existence of an UPSE on a given pointset, which can be tested in $$\mathcal {O}(n \log n)$$ time. Related to this result, we give an algorithm that, for a set S of n points, enumerates all the non-crossing monotone Hamiltonian cycles on S with $$\mathcal {O}(n)$$ worst-case delay, using $$\mathcal {O}(n^2)$$ space, after $$\mathcal {O}(n^2)$$ set-up time.
PubDate: 2025-03-15
-
- Structural Parameterization of Cluster Deletion
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In the Weighted Cluster Deletion problem we are given a graph with non-negative integral edge weights and the task is to determine, for a target value k, if there is a set of edges of total weight at most k such that its removal results in a disjoint union of cliques. It is well-known that the problem is FPT parameterized by k, the total weight of edge deletions. In scenarios in which the solution size is large, naturally one needs to drop the constraint on the solution size. Here we study Weighted Cluster Deletion where the parameter does not represent the size of the solution, but the parameter captures structural properties of the input graph. Our main contribution is to classify the parameterized complexity of Weighted Cluster Deletion with three structural parameters, namely, vertex cover number, twin cover number and neighborhood diversity. We show that the problem is FPT when parameterized by the vertex cover number, whereas it becomes paraNP-hard when parameterized by the twin cover number or the neighborhood diversity. To illustrate the applicability of our FPT result, we turn our attention to the unweighted variant of the problem, namely Cluster Deletion. We show that Cluster Deletion is FPT parameterized by the twin cover number. This is the first algorithm with single-exponential running time parameterized by the twin cover number. Interestingly, we are able to achieve an FPT result for Cluster Deletion parameterized by the neighborhood diversity that involves an ILP formulation. In fact, our results generalize the parameterized setting by the solution size, as we deduce that both parameters, twin cover number and neighborhood diversity, are linearly bounded by the number of edge deletions.
PubDate: 2025-03-15
-
- Improved Algorithms for Distance Selection and Related Problems
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In this paper, we propose new techniques for solving geometric optimization problems involving interpoint distances of a point set in the plane. Given a set P of n points in the plane and an integer $$1 \le k \le \left( {\begin{array}{c}n\\ 2\end{array}}\right) $$, the distance selection problem is to find the k-th smallest interpoint distance among all pairs of points of P. The previously best deterministic algorithm solves the problem in $$O(n^{4/3} \log ^2 n)$$ time (Katz and Sharir in SIAM J Comput 26(5):1384–1408, 1997 and SoCG 1993). In this paper, we improve their algorithm to $$O(n^{4/3} \log n)$$ time. Using similar techniques, we also give improved algorithms on both the two-sided and the one-sided discrete Fréchet distance with shortcuts problem for two point sets in the plane. For the two-sided problem (resp., one-sided problem), we improve the previous work (Avraham et al. in ACM Trans Algorithms 11(4):29, 2015 and SoCG 2014) by a factor of roughly $$\log ^2(m+n)$$ (resp., $$(m+n)^{\epsilon }$$), where m and n are the sizes of the two input point sets, respectively. Other problems whose solutions can be improved by our techniques include the reverse shortest path problems for unit-disk graphs. Our techniques are quite general and we believe they will find many other applications in future.
PubDate: 2025-03-14
-
- On the Parameterized Complexity of Controlling Amendment and Successive
Winners-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: The amendment procedure and the successive procedure have been widely employed in parliamentary and legislative decision making and have undergone extensive study in the literature from various perspectives. However, investigating them through the lens of computational complexity theory has not been as thoroughly conducted as for many other prevalent voting procedures heretofore. To the best of our knowledge, there is only one paper which explores the complexity of several strategic voting problems under these two procedures, prior to our current work. To provide a better understanding of to what extent the two procedures resist strategic behavior, we study the parameterized complexity of constructive/destructive control by adding/deleting voters/candidates for both procedures. To enhance the generalizability of our results, we also examine a more generalized form of the amendment procedure. Our exploration yields a comprehensive (parameterized) complexity landscape of these problems with respect to numerous parameters.
PubDate: 2025-03-13
-
- Online Metric Matching on the Line with Recourse
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In online metric matching on the line, n requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all located on the real line. The goal is to minimize the sum of distances between the requests and their assigned servers. The best known online algorithm achieves a competitive ratio of $$\Theta (\log n)$$, leaving a gap to the best-known lower bound of $$\Omega (\sqrt{\log n})$$. In this work, we approach the problem in a recourse model where online decisions can be partially revised, allowing for the reassignment of previously matched edges. In contrast to the traditional online setting, we show that with an amortized recourse budget of $$O(\log n)$$, we can obtain an O(1)-competitive algorithm for online metric matching on the line. This is one of the first non-trivial results for metric matching with recourse. Additionally, for so-called alternating instances, where no more than one request lies between two servers, we achieve a near-optimal result. Specifically, we give a simple algorithm that is $$(1+\varepsilon )$$-competitive and reassigns any request at most $$O(\frac{1}{\varepsilon ^2})$$ times. This special case is particularly noteworthy, as a lower bound of $$\Omega (\log n)$$, constructed using such instances, applies to a broad class of online algorithms, including all deterministic algorithms studied in the literature.
PubDate: 2025-03-01
-
- Simultaneous Representation of Proper and Unit Interval Graphs
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs—the simultaneous version of arguably one of the most well-studied graph classes—is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more ‘rigid’ and therefore have less freedom in their representation. We show they can be recognized in time $$\mathcal {O}( V \cdot E )$$ for any number of simultaneous graphs in the sunflower case where $$G=(V,E)$$ is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.
PubDate: 2025-02-28
-
- Enumerating Minimal Solution Sets for Metric Graph Problems
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Problems from metric graph theory like Metric Dimension, Geodetic Set, and Strong Metric Dimension have recently had an impact in parameterized complexity by being the first known problems in NP to admit double-exponential lower bounds in the treewidth, and even in the vertex cover number for the latter, assuming the Exponential Time Hypothesis. We initiate the study of enumerating minimal solution sets for these problems and show that they are also of great interest in enumeration. Specifically, we show that enumerating minimal resolving sets in graphs and minimal geodetic sets in split graphs are equivalent to enumerating minimal transversals in hypergraphs (denoted Trans-Enum), whose solvability in total-polynomial time is one of the most important open problems in algorithmic enumeration. This provides two new natural examples to a question that emerged in recent works: for which vertex (or edge) set graph property $$\Pi $$ is the enumeration of minimal (or maximal) subsets satisfying $$\Pi $$ equivalent to Trans-Enum' As very few properties are known to fit within this context—namely, those related to minimal domination—our results make significant progress in characterizing such properties, and provide new angles to approach Trans-Enum. In contrast, we observe that minimal strong resolving sets can be enumerated with polynomial delay. Additionally, we consider cases where our reductions do not apply, namely graphs with no long induced paths, and show both positive and negative results related to the enumeration and extension of partial solutions.
PubDate: 2025-02-25
-
- Counting Temporal Paths
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: This work investigates the parameterised complexity of counting temporal paths. The problem of counting temporal paths is mainly motivated by temporal betweenness computation. The betweenness centrality of a vertex v is an important centrality measure that quantifies how many optimal paths between pairs of other vertices visit v. Computing betweenness centrality in a temporal graph, in which the edge set may change over discrete timesteps, requires us to count temporal paths that are optimal with respect to some criterion. For several natural notions of optimality, including foremost or fastest temporal paths, this counting problem reduces to #Temporal Path, the problem of counting all temporal paths between a fixed pair of vertices; like the problems of counting foremost and fastest temporal paths, #Temporal Path is #P-hard in general. Motivated by the many applications of this intractable problem, we initiate a systematic study of the parameterised and approximation complexity of #Temporal Path. We show that the problem presumably does not admit an FPT-algorithm for the feedback vertex number of the static underlying graph, and that it is hard to approximate in general. On the positive side, we prove several exact and approximate FPT-algorithms for special cases.
PubDate: 2025-02-25
-
- Convergence of the Number of Period sets in Strings
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Consider words of length n. The set of all periods of a word of length n is a subset of $$\{0,1,2,\ldots ,n-1\}$$. However, not every subset of $$\{0,1,2,\ldots ,n-1\}$$ can be a valid set of periods. In a seminal paper in 1981, Guibas and Odlyzko proposed encoding the set of periods of a word into a binary string of length n, called an autocorrelation, where a 1 at position i denotes the period i. They considered the question of recognizing a valid period set, and also studied the number $$\kappa _n$$ of valid period sets for strings of length n. They conjectured that $$\ln \kappa _n$$ asymptotically converges to a constant times $$(\ln n)^2$$. Although improved lower bounds for $$\ln \kappa _n/(\ln n)^2$$ were proved in 2001, the question of a tight upper bound has remained open since Guibas and Odlyzko’s paper. Here, we exhibit an upper bound for this fraction, which implies its convergence and closes this longstanding conjecture. Moreover, we extend our result to find similar bounds for the number of correlations: a generalization of autocorrelations that encodes the overlaps between two strings.
PubDate: 2025-02-21
-
- Analysis of the (1+1) EA on LeadingOnes with Constraints
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Understanding how evolutionary algorithms perform on constrained problems has gained increasing attention in recent years. In this paper, we study how evolutionary algorithms optimize constrained versions of the classical LeadingOnes problem. We first provide a run time analysis for the classical (1+1) EA on the LeadingOnes problem with a deterministic cardinality constraint, giving $$\Theta (n (n-B)\log (B) + nB)$$ as the tight bound. Our results show that the behaviour of the algorithm is highly dependent on the constraint bound of the uniform constraint. Afterwards, we consider the problem in the context of stochastic constraints and provide insights using theoretical and experimental studies on how the ($$\mu $$+1) EA is able to deal with these constraints in a sampling-based setting.
PubDate: 2025-02-19
-
- Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by
Treewidth-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In Chordal/Interval Vertex Deletion we ask how many vertices one needs to remove from a graph to make it chordal (respectively: interval). We study these problems under the parameterization by treewidth $$\textbf{tw}$$ of the input graph G. On the one hand, we present an algorithm for Chordal Vertex Deletion with running time $$2^{\mathcal {O}(\textbf{tw})} \cdot V(G) $$, improving upon the running time $$2^{\mathcal {O}(\textbf{tw}^2)} \cdot V(G) ^{\mathcal {O}(1)}$$ by Jansen, de Kroon, and Włodarczyk (STOC’21). When a tree decomposition of width $$\textbf{tw}$$ is given, then the base of the exponent equals $$2^{\omega -1}\cdot 3 + 1$$. Our algorithm is based on a novel link between chordal graphs and graphic matroids, which allows us to employ the framework of representative families. On the other hand, we prove that Interval Vertex Deletion cannot be solved in time $$2^{o(\textbf{tw}\log \textbf{tw})} \cdot V(G) ^{\mathcal {O}(1)}$$ assuming the Exponential Time Hypothesis.
PubDate: 2025-01-29
-
- Correction: Galloping in Fast-Growth Natural Merge Sorts
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
PubDate: 2025-01-29
-
- Reforming an Envy-Free Matching
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We consider the problem of reforming an envy-free matching when each agent has a strict preference over items and is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain. We also give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.
PubDate: 2025-01-27
-
- Guarding Polyominoes Under k-Hop Visibility
-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We study the Art Gallery Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a $$2\times 2$$ block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a $$3\times 3$$ block of cells) for all $$k\in {\mathbb {N}}$$.
PubDate: 2025-01-11
-
- Fixed Parameter Multi-Objective Evolutionary Algorithms for the
W-Separator Problem-
Free pre-print version: Loading...Rate this result: What is this?Please help us test our new pre-print finding feature by giving the pre-print link a rating.
A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multi-objective algorithms for the W-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most W vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution OPT and W. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the W-separator uses linear programming methods and requires non-trivial post-processing steps to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the W-separator problem.
PubDate: 2025-01-08
-
