1,721,025 research outputs found
Why is it hard to beat for Longest Common Weakly Increasing Subsequence?
Full text linkThe Longest Common Weakly Increasing Subsequence problem (LCWIS) is a variant of the classic Longest Common Subsequence problem (LCS). Both problems can be solved with simple quadratic time algorithms. A recent line of research led to a number of matching conditional lower bounds for LCS and other related problems. However, the status of LCWIS remained open. In this paper we show that LCWIS cannot be solved in O(n2−ε) time unless the Strong Exponential Time Hypothesis (SETH) is false. The ideas which we developed can also be used to obtain a lower bound based on a safer assumption of NC-SETH, i.e. a version of SETH which talks about NC circuits instead of less expressive CNF formulas
Learning-augmented maximum flow
Full text linkWe propose a framework for speeding up maximum flow computation by using predictions. A prediction is a flow, i.e., an assignment of non-negative flow values to edges, which satisfies the flow conservation property, but does not necessarily respect the edge capacities of the actual instance (since these were unknown at the time of learning). We present an algorithm that, given an m-edge flow network and a predicted flow, computes a maximum flow in O(mη) time, where η is the l1 error of the prediction, i.e., the sum over the edges of the absolute difference between the predicted and optimal flow values. Moreover, we prove that, given an oracle access to a distribution over flow networks, it is possible to efficiently PAC-learn a prediction minimizing the expected l1 error over that distribution. Our results fit into the recent line of research on learning-augmented algorithms, which aims to improve over worst-case bounds of classical algorithms by using predictions, e.g., machine-learned from previous similar instances
3SUM in Preprocessed Universes: Faster and Simpler
No full textWe revisit the 3SUM problem in the preprocessed universes setting. We present an algorithm that, given three sets A, B, C of n integers, preprocesses them in quadratic time, so that given any subsets A′⊆A, B′⊆B, C′⊆C, it can decide if there exist a∈A′, b∈B′, c∈C′ with a+b=c in time O(n^1.5 log n). In contrast to both the first subquadratic O~(n^13/7)-time algorithm by Chan and Lewenstein (STOC 2015) and the current fastest O~(n^11/6)-time algorithm by Chan, Vassilevska Williams, and Xu (STOC 2023), which are based on the Balog–Szemerédi–Gowers theorem from additive combinatorics, our algorithm uses only standard 3SUM-related techniques, namely FFT and linear hashing modulo a prime. It is therefore not only faster but also simpler. Just as the two previous algorithms, ours not only decides if there is a single 3SUM solution but it actually determines for each c∈C′ if there is a solution containing it. We also modify the algorithm to still work in the scenario where the set C is unknown at the time of preprocessing. Finally, even though the simplest version of our algorithm is randomized, we show how to make it deterministic losing only polylogarithmic factors in the running time
Sposób i układ do zdalnego pomiaru i rejestracji konwergencji w wyrobiskach górniczych objętych wpływem wstrząsów opis patentowy nr 190357 /
No full textTyt. z ekranu tyt.Nr zgłoszenia P 332354.Zgłoszono 31 marca 1999 r.Zgłoszenie ogłoszono 9 października 2000 r. BUP 20/00.O udzieleniu patentu ogłoszono 30 grudnia 2005 r. WUP 12/05.Pozostali twórcy wynalazku: Zdzisław Kłeczek, Andrzej Malesza, Waldemar Polak, Adam Polak.Dostępny także w wersji drukowanej.Tryb dostępu: Internet
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
Full text linkThe starting point of this paper is the problem of scheduling n jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy jobs, i.e., (Equation presented). This problem was identified by Bringmann et al. (Algorithmica 2022) as a natural subquadratic-time special case of the classic v problem, which likely requires time quadratic in the total processing time P, because of a fine-grained lower bound. Bringmann et al. obtain their (Equation presented) time scheduling algorithm through a new variant of convolution, dubbed Max-Min Skewed Convolution, which they solve in (Equation presented) time. Our main technical contribution is a faster and simpler convolution algorithm running in (Equation presented) time. It implies an (Equation presented) time algorithm for (Equation presented), but may also be of independent interest. Inspired by recent developments for the Subset Sum and Knapsack problems, we study (Equation presented) parameterized by the maximum job processing time pmax. With proximity techniques borrowed from integer linear programming (ILP), we show structural properties of the problem that, coupled with a new dynamic programming formulation, lead to an (Equation presented) time algorithm. Moreover, in the setting with multiple machines, we use similar techniques to get an (Equation presented) time algorithm for (Equation presented). Finally, we point out that the considered problems exhibit a particular triangular block structure in the constraint matrices of their ILP formulations. In light of recent ILP research, a question that arises is whether one can devise a generic algorithm for such a class of ILPs. We give a negative answer to this question: we show that already a slight generalization of the structure of the scheduling ILP leads to a strongly NP-hard problem.</p
Bellman-Ford is optimal for shortest hop-bounded paths
Full text linkThis paper is about the problem of finding a shortest - path using at
most edges in edge-weighted graphs. The Bellman--Ford algorithm solves this
problem in time, where is the number of edges. We show that this
running time is optimal, up to subpolynomial factors, under popular
fine-grained complexity assumptions.
More specifically, we show that under the APSP Hypothesis the problem cannot
be solved faster already in undirected graphs with non-negative edge weights.
This lower bound holds even restricted to graphs of arbitrary density and for
arbitrary . Moreover, under a stronger assumption, namely
the Min-Plus Convolution Hypothesis, we can eliminate the restriction . In other words, the bound is tight for the entire space
of parameters , , and , where is the number of nodes.
Our lower bounds can be contrasted with the recent near-linear time algorithm
for the negative-weight Single-Source Shortest Paths problem, which is the
textbook application of the Bellman--Ford algorithm
- …
