Recent zbMATH articles in MSC 68Whttps://www.zbmath.org/atom/cc/68W2021-02-12T15:23:00+00:00WerkzeugScheduling to minimize total weighted completion time via time-indexed linear programming relaxations.https://www.zbmath.org/1452.682772021-02-12T15:23:00+00:00"Li, Shi"https://www.zbmath.org/authors/?q=ai:li.shiOn efficient distributed construction of near optimal routing schemes.https://www.zbmath.org/1452.680172021-02-12T15:23:00+00:00"Elkin, Michael"https://www.zbmath.org/authors/?q=ai:elkin.michael"Neiman, Ofer"https://www.zbmath.org/authors/?q=ai:neiman.oferSummary: Given a distributed network represented by a weighted undirected graph \(G=(V,E)\) on \(n\) vertices, and a parameter \(k\), we devise a randomized distributed algorithm that whp computes a routing scheme in \(O(n^{1/2+1/k}+D)\cdot n^{o(1)}\) rounds, where \(D\) is the hop-diameter of the network. Moreover, for odd \(k\), the running time of our algorithm is \(O(n^{1/2+1/(2k)}+D) \cdot n^{o(1)}\). Our running time nearly matches the lower bound of \(\tilde{\Omega}(n^{1/2}+D)\) rounds (which holds for any scheme with polynomial stretch). The routing tables are of size \(\tilde{O}(n^{1/k})\), the labels are of size \(O(k\log ^2n)\), and every packet is routed on a path suffering stretch at most \(4k-5+o(1)\). Our construction nearly matches the state-of-the-art for routing schemes built in a centralized sequential manner. The previous best algorithms for building routing tables in a distributed small messages model were
by \textit{C. Lenzen} and \textit{B. Patt-Shamir} [in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC'13. New York, NY: Association for Computing Machinery (ACM). 381--390 (2013; Zbl 1293.68058); in: Proceedings of the 34th ACM symposium on principles of distributed computing, PODC'15. New York, NY: Association for Computing Machinery (ACM). 153--162 (2015; Zbl 1333.68280)].
The former has similar properties but suffers from substantially larger routing tables of size \(O(n^{1/2+1/k})\), while the latter has sub-optimal running time of \(\tilde{O}(\min \{(nD)^{1/2}\cdot n^{1/k},n^{2/3+2/(3k)}+D\})\).On the power of statistical zero knowledge.https://www.zbmath.org/1452.680812021-02-12T15:23:00+00:00"Bouland, Adam"https://www.zbmath.org/authors/?q=ai:bouland.adam"Chen, Lijie"https://www.zbmath.org/authors/?q=ai:chen.lijie"Holden, Dhiraj"https://www.zbmath.org/authors/?q=ai:holden.dhiraj"Thaler, Justin"https://www.zbmath.org/authors/?q=ai:thaler.justin"Vasudevan, Prashant Nalini"https://www.zbmath.org/authors/?q=ai:vasudevan.prashant-naliniDiophantine tori and pragmatic calculation of quasimodes for operators with integrable principal symbol.https://www.zbmath.org/1452.370712021-02-12T15:23:00+00:00"Anikin, A. Yu."https://www.zbmath.org/authors/?q=ai:anikin.a-yu"Dobrokhotov, S. Yu."https://www.zbmath.org/authors/?q=ai:dobrokhotov.sergei-yuThe authors study the asymptotic eigenfunctions (quasimodes) of a semi-classical Weyl pseudo-differential operator. According to a well-known method (see [\textit{V. Ivrii}, Microlocal analysis and precise spectral asymptotics. Berlin: Springer (1998; Zbl 0906.35003)]), under the assumption of complete integrability for the Hamiltonian, the phase space is foliated into a family of invariant tori, so that one can study the quasimodes. The authors observe that such an approach is not very efficient for practical calculations and they propose a new method for operators with integrable principal symbol. As an example, they consider the case of a two weakly coupled oscillators. A Diophantine torus is then chosen and their algorithm can be applied. By using a mathematical software like Wolfram Mathematica, the quasimodes can be explicitly constructed.
Reviewer: Luigi Rodino (Torino)Maximum generalized assignment with convex costs.https://www.zbmath.org/1452.902002021-02-12T15:23:00+00:00"Bender, Marco"https://www.zbmath.org/authors/?q=ai:bender.marco"Westphal, Stephan"https://www.zbmath.org/authors/?q=ai:westphal.stephanSummary: We consider a generalization of the maximum generalized assignment problem. We relax the hard constraints for the bin capacities, and introduce for every bin a cost function that is convex in the total load on this bin. These costs are subtracted from the profits of assigned items, and the task is to find an assignment maximizing the resulting net profit.{
}We show that even restricted cases of this problem remain strongly NP-complete, and identify two cases that can be solved in strongly polynomial time. Furthermore, we present a \((1-1/e)\)-approximation algorithm for the general case. This algorithm uses a configuration based integer programming formulation for a randomized rounding procedure. In order to turn the rounded solution into a feasible solution, we define appropriate estimators that linearize the convex costs.
For the entire collection see [Zbl 1319.90005].Improving multi-armed bandit algorithms in online pricing settings.https://www.zbmath.org/1452.911552021-02-12T15:23:00+00:00"Trovò, Francesco"https://www.zbmath.org/authors/?q=ai:trovo.francesco"Paladino, Stefano"https://www.zbmath.org/authors/?q=ai:paladino.stefano"Restelli, Marcello"https://www.zbmath.org/authors/?q=ai:restelli.marcello"Gatti, Nicola"https://www.zbmath.org/authors/?q=ai:gatti.nicolaSummary: The design of effective bandit algorithms to learn the optimal price is a task of extraordinary importance in all the settings in which the demand curve is not \textit{a priori} known and the estimation process takes a long time, as customary, e.g., in e-commerce scenarios. In particular, the adoption of effective pricing algorithms may allow companies to increase their profits dramatically. In this paper, we exploit the structure of the pricing problem in online scenarios to improve the performance of state-of-the-art general-purpose bandit algorithms. More specifically, we make use of the \textit{monotonicity} of the customer demand curve, which suggests the same behavior of the conversion rates, and we exploit the fact that, in many scenarios, companies have \textit{a priori information} about the order of magnitude of the conversion rate. We design techniques -- applicable in principle to any bandit algorithm -- capable of exploiting these two properties, and we apply them to upper confidence bound policies both in stationary and nonstationary environments. We show that algorithms exploiting these two properties may significantly outperform state-of-the-art bandit policies in most of the configurations and we also show that the improvement increases as the number of arms increases. In particular, simulations based on real-world data show that our algorithms may increase the profit by \(300\%\) or more when compared to the performance achieved by state-of-the-art bandit algorithms. Furthermore, we formally prove that the empirical improvement provided by our algorithms can be achieved without incurring any cost in terms of theoretical guarantees. Indeed, our algorithms present the same asymptotic worst-case regret bounds of the bandit algorithms previously known in the state of the art.Proceedings of the 39th ACM symposium on principles of distributed computing, PODC '20, virtual event, August 3--7, 2020.https://www.zbmath.org/1452.680062021-02-12T15:23:00+00:00"Cachin, Christian (ed.)"https://www.zbmath.org/authors/?q=ai:cachin.christian"Emek, Yuval (ed.)"https://www.zbmath.org/authors/?q=ai:emek.yuvalThe articles of this volume will be reviewed individually. For the preceding symposium see [Zbl 1423.68033].Proceedings of the 45th international symposium on symbolic and algebraic computation, ISSAC '20, Kalamata, Greece, July 20--23, 2020.https://www.zbmath.org/1452.680112021-02-12T15:23:00+00:00"Mantzaflaris, Angelos (ed.)"https://www.zbmath.org/authors/?q=ai:mantzaflaris.angelosThe articles of this volume will be reviewed individually. For the preceding symposium see [Zbl 1423.68017].
Indexed articles:
\textit{Cox, David A.}, Reflections on elimination theory, 1-4 [Zbl 07300043]
\textit{Dickenstein, Alicia}, Positive solutions of sparse polynomial systems, 5-7 [Zbl 07300044]
\textit{Lim, Lek-Heng; Ye, Ke}, Ubiquity of the exponent of matrix multiplication, 8-11 [Zbl 07300045]
\textit{Cuyt, Annie}, What do sparse interpolation, Padé approximation, Gaussian quadrature and tensor decomposition have in common?, 12 [Zbl 07300046]
\textit{England, Matthew}, Real quantifier elimination by cylindrical algebraic decomposition, and improvements by machine learning, 13 [Zbl 07300047]
\textit{Abelard, Simon; Couvreur, Alain; Lecerf, Grégoire}, Sub-quadratic time for Riemann-Roch spaces. Case of smooth divisors over nodal plane projective curves, 14-21 [Zbl 07300048]
\textit{Asadi, Mohammadali; Brandt, Alexander; Moir, Robert H. C.; Maza, Marc Moreno; Xie, Yuzhen}, On the parallelization of triangular decompositions, 22-29 [Zbl 07300049]
\textit{Betten, Anton}, The orbiter ecosystem for combinatorial data, 30-37 [Zbl 07300050]
\textit{Birmpilis, Stavros; Labahn, George; Storjohann, Arne}, A Las Vegas algorithm for computing the Smith form of a nonsingular integer matrix, 38-45 [Zbl 07300051]
\textit{Bostan, Alin}, Computing the N-th term of a q-holonomic sequence, 46-53 [Zbl 07300052]
\textit{Buchacher, Manfred; Kauers, Manuel; Pogudin, Gleb}, Separating variables in bivariate polynomial ideals, 54-61 [Zbl 07300053]
\textit{Capco, Jose; Din, Mohab Safey El; Schicho, Josef}, Robots, computer algebra and eight connected components, 62-69 [Zbl 07300054]
\textit{Caruso, Xavier; Vaccon, Tristan; Verron, Thibaut}, Signature-based algorithms for Gröbner bases over Tate algebras, 70-77 [Zbl 07300055]
\textit{Charalambous, Hara; Karagiannis, Kostas; Karanikolopoulos, Sotiris; Kontogeorgis, Aristides}, Syzygies of ideals of polynomial rings over principal ideal domains, 78-82 [Zbl 07300056]
\textit{Chenavier, Cyrille; Hofstadler, Clemens; Raab, Clemens G.; Regensburger, Georg}, Compatible rewriting of noncommutative polynomials for proving operator identities, 83-90 [Zbl 07300057]
\textit{Chen, Shaoshi; Du, Lixin; Kauers, Manuel; Verron, Thibaut}, Integral bases for P-recursive sequences, 91-98 [Zbl 07300058]
\textit{Chyzak, Frédéric; Dumas, Philippe}, A Gröbner-basis theory for divide-and-conquer recurrences, 99-106 [Zbl 07300059]
\textit{Cortadellas, Teresa; D'Andrea, Carlos; Montoro, M. Eulàlia}, Bounds for degrees of minimal \(\mu\)-bases of parametric surfaces, 107-113 [Zbl 07300060]
\textit{Dahan, Xavier; Vaccon, Tristan}, On a non-Archimedean Broyden method, 114-121 [Zbl 07300061]
\textit{Diekert, Volker; Potapov, Igor; Semukhin, Pavel}, Decidability of membership problems for flat rational subsets of \(\mathrm{GL}(2, \mathbb{Q})\) and singular matrices, 122-129 [Zbl 07300062]
\textit{DiPasquale, Michael; Flores, Zachary; Peterson, Chris}, On the apolar algebra of a product of linear forms, 130-137 [Zbl 07300063]
\textit{Dressler, Mareike; Heuer, Janin; Naumann, Helen; de Wolff, Timo}, Global optimization via the dual SONC cone and linear programming, 138-145 [Zbl 07300064]
\textit{Du, Hao; Guo, Jing; Li, Ziming; Wong, Elaine}, An additive decomposition in logarithmic towers and beyond, 146-153 [Zbl 07300065]
\textit{Duff, Timothy; Ruddy, Michael}, Numerical equality tests for rational maps and signatures of curves, 154-161 [Zbl 07300066]
\textit{Dumas, Jean-Guillaume; Pernet, Clément; Sedoglavic, Alexandre}, On fast multiplication of a matrix by its transpose, 162-169 [Zbl 07300067]
\textit{Elliott, Jesse; Giesbrecht, Mark; Schost, Éric}, On the bit complexity of finding points in connected components of a smooth real hypersurface, 170-177 [Zbl 07300068]
\textit{Falkensteiner, Sebastian; Garay-López, Cristhian; Haiech, Mercedes; Noordman, Marc Paul; Toghani, Zeinab; Boulier, François}, The fundamental theorem of tropical partial differential algebraic geometry, 178-185 [Zbl 07300069]
\textit{Garg, Abhibhav; Saxena, Nitin}, Special-case algorithms for blackbox radical membership, Nullstellensatz and transcendence degree, 186-193 [Zbl 07300070]
\textit{Giesbrecht, Mark; Huang, Qiao-Long; Schost, Éric}, Sparse multiplication for skew polynomials, 194-201 [Zbl 07300071]
\textit{Giorgi, Pascal; Grenet, Bruno; Perret du Cray, Armelle}, Essentially optimal sparse polynomial multiplication, 202-209 [Zbl 07300072]
\textit{Giorgi, Pascal; Grenet, Bruno; Roche, Daniel S.}, Fast in-place algorithms for polynomial operations: division, evaluation, interpolation, 210-217 [Zbl 07300073]
\textit{Groh, Friedemann}, Subdivisions for Macaulay formulas of sparse systems, 218-225 [Zbl 07300074]
\textit{Guerrini, Eleonora; Lebreton, Romain; Zappatore, Ilaria}, On the uniqueness of simultaneous rational function reconstruction, 226-233 [Zbl 07300075]
\textit{Hone, Andrew}, Efficient ECM factorization in parallel with the lyness map, 234-240 [Zbl 07300076]
\textit{Huang, Bo}, Algorithmic averaging for studying periodic orbits of planar differential systems, 241-248 [Zbl 07300077]
\textit{Imbach, Rémi; Pan, Victor Y.}, New progress in univariate polynomial root finding, 249-256 [Zbl 07300078]
\textit{Ishihara, Yuki; Vaccon, Tristan; Yokoyama, Kazuhiro}, On FGLM algorithms with tropical Gröbner bases, 257-264 [Zbl 07300079]
\textit{Ishihara, Yuki}, Modular techniques for effective localization and double ideal quotient, 265-272 [Zbl 07300080]
\textit{Jindal, Gorav; Pandey, Anurag; Shukla, Himanshu; Zisopoulos, Charilaos}, How many zeros of a random sparse polynomial are real?, 273-280 [Zbl 07300081]
\textit{Katsamaki, Christina; Rouillier, Fabrice; Tsigaridas, Elias; Zafeirakopoulos, Zafeirakis}, On the geometry and the topology of parametric curves, 281-288 [Zbl 07300082]
\textit{Kenison, George; Lipton, Richard; Ouaknine, Joël; Worrell, James}, On the Skolem problem and prime powers, 289-296 [Zbl 07300083]
\textit{Le, Huu Phuoc; Din, Mohab Safey El; de Wolff, Timo}, Computing the real isolated points of an algebraic hypersurface, 297-304 [Zbl 07300084]
\textit{Levandovskyy, Viktor; Schönemann, Hans; Zeid, Karim Abou}, \textsc{Letterplace} -- a subsystem of \textsc{Singular} for computations with free algebras via letterplace embedding, 305-311 [Zbl 07300085]
\textit{Levandovskyy, Viktor; Metzlaff, Tobias; Zeid, Karim Abou}, Computation of free non-commutative Gröbner bases over \(\mathbb{Z}\) with \textsc{Singular:Letterplace}, 312-319 [Zbl 07300086]
\textit{Levin, Alexander}, Some properties of multivariate differential dimension polynomials and their invariants, 320-327 [Zbl 07300087]
\textit{Lu, Dong; Wang, Dingkang; Xiao, Fanghui}, Further results on the factorization and equivalence for multivariate polynomial matrices, 328-335 [Zbl 07300088]
\textit{Mantzaflaris, Angelos; Mourrain, Bernard; Szanto, Agnes}, Punctual Hilbert scheme and certified approximate singularities, 336-343 [Zbl 07300089]
\textit{Mathieu-Mahias, Axel; Quisquater, Michaël}, Fast multipoint evaluation and interpolation of polynomials in the LCH-basis over \(\mathbb{F}_P^r\), 344-351 [Zbl 07300090]
\textit{Melquiond, Guillaume; Rieu-Helft, Raphaël}, WhyMP, a formally verified arbitrary-precision integer library, 352-359 [Zbl 07300091]
\textit{Miasnikov, Alexei; Nikolaev, Andrey}, On parameterized complexity of the word search problem in the Baumslag-Gersten group, 360-363 [Zbl 07300092]
\textit{Mou, Chenqi}, On the chordality of ordinary differential triangular decomposition in top-down style, 364-371 [Zbl 07300093]
\textit{Nagasaka, Kosaku}, Approximate GCD by Bernstein basis, and its applications, 372-379 [Zbl 07300094]
\textit{Naldi, Simone; Neiger, Vincent}, A divide-and-conquer algorithm for computing Gröbner bases of syzygies in finite dimension, 380-387 [Zbl 07300095]
\textit{Neiger, Vincent; Rosenkilde, Johan; Solomatov, Grigory}, Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation, 388-395 [Zbl 07300096]
\textit{Oliveira, Rafael}, Conditional lower bounds on the spectrahedral representation of explicit hyperbolicity cones, 396-401 [Zbl 07300097]
\textit{Bazan, Erick Rodriguez; Hubert, Evelyne}, Ideal interpolation, H-bases and symmetry, 402-409 [Zbl 07300098]
\textit{Sharma, Vikram}, Generalizing the Davenport-Mahler-Mignotte bound. The weighted case, 410-417 [Zbl 07300099]
\textit{Sottile, Frank}, General witness sets for numerical algebraic geometry, 418-425 [Zbl 07300100]
\textit{Teramoto, Hiroshi; Nabeshima, Katsusuke}, Parametric standard system for mixed module and its application to singularity theory, 426-433 [Zbl 07300101]
\textit{Tonelli-Cueto, Josué; Tsigaridas, Elias}, Condition numbers for the cube. I: Univariate polynomials and hypersurfaces, 434-441 [Zbl 07300102]
\textit{Wang, Dingkang; Wang, Hesong; Xiao, Fanghui}, An extended GCD algorithm for parametric univariate polynomials and application to parametric Smith normal form, 442-449 [Zbl 07300103]
\textit{Wang, Jie; Magron, Victor}, A second order cone characterization for sums of nonnegative circuits, 450-457 [Zbl 07300104]
\textit{Zeng, Zhonggang}, Geometric modeling and regularization of algebraic problems, 458-465 [Zbl 07300105]Improved bound for dilation of an embedding onto circulant networks.https://www.zbmath.org/1452.681402021-02-12T15:23:00+00:00"Rajan, R. Sundara"https://www.zbmath.org/authors/?q=ai:rajan.r-sundara"Rajalaxmi, T. M."https://www.zbmath.org/authors/?q=ai:rajalaxmi.t-m"Ryan, Joe"https://www.zbmath.org/authors/?q=ai:ryan.joe"Miller, Mirka"https://www.zbmath.org/authors/?q=ai:miller.mirkaSummary: Implementation of parallel algorithms and simulation of different interconnection networks need an effective tool, that is, graph embedding. This paper focuses on improving a lower bound obtained in
[the first author et al., ``A lower bound for dilation of an embedding'', Comput. J. 58, No. 12, 3271--3278 (2015; \url{doi:10.1093/comjnl/bxv021})]
for dilation of an embedding onto circulant networks. In addition, this paper provides algorithms to compute dilation of embedding circulant network into certain trees, for instance, \(m\)-rooted complete binary tree, \(m\)-rooted sibling tree, and \(r\)-dimensional hypertree, proving that the improved bound obtained is sharp.
For the entire collection see [Zbl 1410.65005].A review of literature on parallel constraint solving.https://www.zbmath.org/1452.681772021-02-12T15:23:00+00:00"Gent, Ian P."https://www.zbmath.org/authors/?q=ai:gent.ian-philip"Miguel, Ian"https://www.zbmath.org/authors/?q=ai:miguel.ian"Nightingale, Peter"https://www.zbmath.org/authors/?q=ai:nightingale.peter-w"McCreesh, Ciaran"https://www.zbmath.org/authors/?q=ai:mccreesh.ciaran"Prosser, Patrick"https://www.zbmath.org/authors/?q=ai:prosser.patrick"Moore, Neil C. A."https://www.zbmath.org/authors/?q=ai:moore.neil-c-a"Unsworth, Chris"https://www.zbmath.org/authors/?q=ai:unsworth.chrisSummary: As multi-core computing is now standard, it seems irresponsible for constraints researchers to ignore the implications of it. Researchers need to address a number of issues to exploit parallelism, such as: investigating which constraint algorithms are amenable to parallelisation; whether to use shared memory or distributed computation; whether to use static or dynamic decomposition; and how to best exploit portfolios and cooperating search. We review the literature, and see that we can sometimes do quite well, some of the time, on some instances, but we are far from a general solution. Yet there seems to be little overall guidance that can be given on how best to exploit multi-core computers to speed up constraint solving. We hope at least that this survey will provide useful pointers to future researchers wishing to correct this situation.Efficient convex optimization with oracles.https://www.zbmath.org/1452.682722021-02-12T15:23:00+00:00"Lee, Yin Tat"https://www.zbmath.org/authors/?q=ai:lee.yin-tat"Sidford, Aaron"https://www.zbmath.org/authors/?q=ai:sidford.aaron"Vempala, Santosh S."https://www.zbmath.org/authors/?q=ai:vempala.santosh-sSummary: Minimizing a convex function over a convex set is a basic algorithmic problem. We give a simple algorithm for the general setting in which the function is given by an evaluation oracle and the set by a membership oracle. The algorithm takes \(\widetilde{O}(n^2)\) oracle calls and \(\widetilde{O}(n^3)\) additional arithmetic operations. This results in more efficient reductions among the five basic oracles for convex sets and functions defined by
\textit{M. Grötschel} et al. [Geometric algorithms and combinatorial optimization. Berlin etc.: Springer-Verlag (1988; Zbl 0634.05001)].
For the entire collection see [Zbl 1443.05002].Almost event-rate independent monitoring of metric temporal logic.https://www.zbmath.org/1452.682782021-02-12T15:23:00+00:00"Basin, David"https://www.zbmath.org/authors/?q=ai:basin.david-a"Bhatt, Bhargav Nagaraja"https://www.zbmath.org/authors/?q=ai:bhatt.bhargav-nagaraja"Traytel, Dmitriy"https://www.zbmath.org/authors/?q=ai:traytel.dmitrySummary: A monitoring algorithm is trace-length independent if its space consumption does not depend on the number of events processed. The analysis of many monitoring algorithms has aimed at establishing trace-length independence. But a trace-length independent monitor's space consumption can depend on characteristics of the trace other than its size.
We put forward the stronger notion of event-rate independence, where the monitor's space usage does not depend on the event rate. This property is critical for monitoring voluminous streams of events arriving at a varying rate. Some previously proposed algorithms for past-only temporal logics satisfy this new property. However, when dealing with future operators, the traditional approach of using a queue to wait for future obligations to be resolved is not event-rate independent. We propose a new algorithm that supports metric past and bounded future operators and is almost event-rate independent, where ``almost'' denotes a logarithmic dependence on the event rate: the algorithm must store the event rate as a number. We compare our algorithm with traditional ones, providing evidence that almost event-rate independence matters in practice.
For the entire collection see [Zbl 1360.68016].Mixed fault tolerance in server assignment: combining reinforcement and backup.https://www.zbmath.org/1452.680282021-02-12T15:23:00+00:00"Navon, Tal"https://www.zbmath.org/authors/?q=ai:navon.tal"Peleg, David"https://www.zbmath.org/authors/?q=ai:peleg.davidSummary: We study the mixed approach to fault tolerance in the general context of server assignment in networks. The approach is based on mixing two different existing strategies, namely, reinforcement and backup. The former strategy protects clients by reinforcing the servers assigned to them and making them fault-resistant, possibly at a high cost, while the latter protects clients by assigning to them alternate low price backup servers that can replace their primary servers in case those fail. Applying the mixed approach to fault tolerance gives rise to new fault tolerant variations of known server assignment problems. We introduce several NP-hard problems of this type, including the mixed fault-tolerant dominating set problem, the mixed fault-tolerant centers problem, and the mixed fault-tolerant facility location problem, and present polynomial time approximation algorithms for them, demonstrating the viability of the mixed strategy for server assignment problems.Subspace arrangements, graph rigidity and derandomization through submodular optimization.https://www.zbmath.org/1452.680892021-02-12T15:23:00+00:00"Raz, Orit E."https://www.zbmath.org/authors/?q=ai:raz.orit-e"Wigderson, Avi"https://www.zbmath.org/authors/?q=ai:wigderson.aviSummary: This paper presents a deterministic, strongly polynomial time algorithm for computing the matrix rank for a class of symbolic matrices (whose entries are polynomials over a field). This class was introduced, in a different language, by
\textit{L. Lovász} [in: Proceedings of the 6th British combinatorics conference. London, etc: Academic Press. 45--86 (1977; Zbl 0361.05027)]
in his study of flats in matroids, and proved a duality theorem putting this problem in \(\mathrm{NP}\cap\mathrm{coNP}\). As such, our result is another demonstration where ``good characterization'' in the sense of Edmonds leads to an efficient algorithm. In a different paper
\textit{L. Lovász} [in: Fundamentals of computation theory -- FCT '79. Proceedings of the conference on algebraic, arithmetic, and categorial methods in computation theory held in Berlin/Wendisch-Rietz (GDR). Berlin: Akademie-Verlag. 565--574 (1979; Zbl 0446.68036)]
proved that all such symbolic rank problems have efficient probabilistic algorithms, namely are in BPP. As such, our algorithm may be interpreted as a derandomization result, in the long sequence special cases of the PIT (Polynomial Identity Testing) problem. Finally,
\textit{L. Lovász} and \textit{Y. Yemini} [SIAM J. Algebraic Discrete Methods 3, 91--98 (1982; Zbl 0497.05025)]
showed how the same problem generalizes the \textit{graph rigidity} problem in two dimensions. As such, our algorithm may be seen as a generalization of the well-known deterministic algorithm for the latter problem. There are two somewhat unusual technical features in this paper. The first is the translation of Lovász' flats problem into a symbolic rank one. The second is the use of submodular optimization for derandomization. We hope that the tools developed for both will be useful for related problems, in particular for better understanding of graph rigidity in higher dimensions.
For the entire collection see [Zbl 1443.05002].Toward a preconditioned scalable 3DVAR for assimilating sea surface temperature collected into the Caspian Sea.https://www.zbmath.org/1452.860042021-02-12T15:23:00+00:00"Arcucci, R."https://www.zbmath.org/authors/?q=ai:arcucci.rossella"Carracciuolo, L."https://www.zbmath.org/authors/?q=ai:carracciuolo.luisa"Toumi, R."https://www.zbmath.org/authors/?q=ai:toumi.ralfSummary: Data Assimilation (DA) is an uncertainty quantification technique used to incorporate observed data into a prediction model in order to improve numerical forecasted results. As a crucial point into DA models is the ill conditioning of the covariance matrices involved, it is mandatory to introduce, in a DA software, preconditioning methods. Here we present first results obtained introducing two different preconditioning methods in a DA software we are developing (we named S3DVAR) which implements a Scalable Three Dimensional Variational Data Assimilation model for assimilating sea surface temperature (SST) values collected into the Caspian Sea by using the Regional Ocean Modeling System (ROMS) with observations provided by the Group of High resolution sea surface temperature (GHRSST). We present the algorithmic strategies we employ and the numerical issues on data collected in two of the months which present the most significant variability in water temperature: August and March.Efficient randomized test-and-set implementations.https://www.zbmath.org/1452.682682021-02-12T15:23:00+00:00"Giakkoupis, George"https://www.zbmath.org/authors/?q=ai:giakkoupis.george"Woelfel, Philipp"https://www.zbmath.org/authors/?q=ai:woelfel.philippSummary: We study randomized test-and-set (TAS) implementations from registers in the asynchronous shared memory model with \(n\) processes. We introduce the problem of \textit{group election}, a natural variant of leader election, and propose a framework for the implementation of TAS objects from group election objects. We then present two group election algorithms, each yielding an efficient TAS implementation. The first implementation has expected max-step complexity \(O(\log ^*k)\) in the location-oblivious adversary model, and the second has expected max-step complexity \(O(\log \log k)\) against any read/write-oblivious adversary, where \(k\le n\) is the contention. These algorithms improve the previous upper bound
by \textit{D. Alistarh} and \textit{J. Aspnes} [Lect. Notes Comput. Sci. 6950, 97--109 (2011; Zbl 1302.68310)]
of \(O(\log \log n)\) expected max-step complexity in the oblivious adversary model. We also propose a modification to a TAS algorithm devised
by \textit{D. Alistarh} et al. [Lect. Notes Comput. Sci. 6343, 94--108 (2010; Zbl 1302.68311)]
for the strong adaptive adversary, which improves its space complexity from super-linear to linear, while maintaining its \(O(\log n)\) expected max-step complexity. We then describe how this algorithm can be combined with any randomized TAS algorithm that has expected max-step complexity \(T(n)\) in a weaker adversary model, so that the resulting algorithm has \(O(\log n)\) expected max-step complexity against any strong adaptive adversary and \(O(T(n))\) in the weaker adversary model. Finally, we prove that for any randomized 2-process TAS algorithm, there exists a schedule determined by an oblivious adversary such that with probability at least \(1/4^t\) one of the processes needs at least \(t\) steps to finish its TAS operation. This complements a lower bound
by \textit{H. Attiya} and \textit{K. Censor-Hillel} [SIAM J. Comput. 39, No. 8, 3885--3904 (2010; Zbl 1214.68241)]
on a similar problem for \(n\ge 3\) processes.The parameterised complexity of computing the maximum modularity of a graph.https://www.zbmath.org/1452.680912021-02-12T15:23:00+00:00"Meeks, Kitty"https://www.zbmath.org/authors/?q=ai:meeks.kitty"Skerman, Fiona"https://www.zbmath.org/authors/?q=ai:skerman.fionaSummary: The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be \textsf{NP}-complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph \(G\). We show that the problem belongs to \textsf{FPT} when parameterised by the size of a minimum vertex cover for \(G\), and is solvable in polynomial time whenever the treewidth or max leaf number of \(G\) is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set.Ordered and delayed adversaries and how to work against them on a shared channel.https://www.zbmath.org/1452.682702021-02-12T15:23:00+00:00"Klonowski, Marek"https://www.zbmath.org/authors/?q=ai:klonowski.marek"Kowalski, Dariusz R."https://www.zbmath.org/authors/?q=ai:kowalski.dariusz-r"Mirek, Jarosław"https://www.zbmath.org/authors/?q=ai:mirek.jaroslawSummary: An execution of a distributed algorithm is often seen as a game between the algorithm and a conceptual adversary causing specific distractions to the computation. In this work we define a class of \textit{ordered adaptive adversaries}, which cause distractions -- in particular crashes -- online according to some partial order of the participating stations, which is fixed by the adversary before the execution. We distinguish: \textit{Linearly-Ordered adversary}, restricted by some pre-defined \textit{linear} order of (potentially) crashing stations; \textit{Anti-Chain-Ordered adversary}, previously known as the \textit{Weakly-Adaptive adversary}, which is restricted by some pre-defined \textit{set} of crash-prone stations (it can be seen as an ordered adversary with the order being an anti-chain, i.e., a collection of incomparable elements, consisting of these stations); \(k\)-\textit{Thick-Ordered adversary} restricted by \textit{partial orders} of stations with a maximum anti-chain of size \(k\). We initiate a study of how they affect performance of algorithms. For this purpose, we focus on the well-known Do-All problem of performing \(t\) tasks by \(p\) synchronous crash-prone stations communicating on a shared channel. The channel restricts communication by the fact that no message is delivered to the operational stations if more than one station transmits at the same time. The question addressed in this work is how the ordered adversaries controlling crashes of stations influence work performance, defined as the total number of available processor steps during the whole execution and introduced by
\textit{P. C. Kanellakis} and \textit{A. A. Shvartsman} [Distrib. Comput. 5, No. 4, 201--217 (1992; Zbl 0744.68060)]
in the context of Write-All algorithms. The first presented algorithm solves the Do-All problem with work \({\mathcal{O}}(t+p \sqrt{t}\log p)\) against the Linearly-Ordered adversary. Surprisingly, the upper bound on performance of this algorithm does not depend on the number of crashes \(f\) and is close to the absolute lower bound \(\varOmega (t+p\sqrt{t})\) proved
in [\textit{B. S. Chlebus} et al., Distrib. Comput. 18, No. 6, 435--451 (2006; Zbl 1266.68207)].
Another algorithm is developed against the Weakly-Adaptive adversary. Work done by this algorithm is \(\mathcal{O}(t + p\sqrt{t} + p\min \left\{ p/(p-f),t\right\} \log p ),\) which is close to the lower bound \(\varOmega (t + p\sqrt{t} + p\min \left\{ p/(p-f),t\right\} )\) proved in [Chlebus, loc. cit.]
and answers the open questions posed there. We generalize this result to the class of \(k\)-Thick-Ordered adversaries, in which case the work of the algorithm is bounded by \(\mathcal{O}(t + p\sqrt{t} + p\min \left\{ p/(p-f),k,t\right\} \log p ).\) We complement this result by proving the almost matching lower bound \(\varOmega (t + p\sqrt{t} + p\min \{ p/(p-f),k,t\} ).\) Independently from the results for the ordered adversaries, we consider a class of \textit{delayed adaptive adversaries}, which could see random choices with some delay. We present an algorithm that works efficiently against the \textit{1-RD} adversary, which could see random choices of stations with one round delay, achieving close to optimal \({\mathcal{O}}(t+p \sqrt{t}\log ^2 p)\) work complexity. This shows that restricting the adversary by not allowing it to react on random decisions immediately makes it significantly weaker, in the sense that there is an algorithm achieving (almost) optimal work performance.Exact periodic cross-kink wave solutions for the \((2+1)\)-dimensional Korteweg-de Vries equation.https://www.zbmath.org/1452.350622021-02-12T15:23:00+00:00"Liu, Jian-Guo"https://www.zbmath.org/authors/?q=ai:liu.jian-guo|liu.jian-guo.1"Ye, Qing"https://www.zbmath.org/authors/?q=ai:ye.qingSummary: The movement of any object has a certain natural law, and the studies and solutions to many natural laws boil down to the problem of mathematical physics equations. Many important physical situations such as fluid flows, plasma physics, and solid state physics have been described by the Korteweg-de Vries (KdV)-type models. In this article, the \((2+1)\)-dimensional KdV equation is presented. By using the Hirota's bilinear form and the extended Ansätz function method, we obtain new exact periodic cross-kink wave solutions for the \((2+1)\)-dimensional KdV equation. With the aid of symbolic computation, the properties for these exact periodic cross-kink wave solutions are shown with some figures.Algebraic methods in the congested clique.https://www.zbmath.org/1452.682672021-02-12T15:23:00+00:00"Censor-Hillel, Keren"https://www.zbmath.org/authors/?q=ai:censor-hillel.keren"Kaski, Petteri"https://www.zbmath.org/authors/?q=ai:kaski.petteri"Korhonen, Janne H."https://www.zbmath.org/authors/?q=ai:korhonen.janne-h"Lenzen, Christoph"https://www.zbmath.org/authors/?q=ai:lenzen.christoph"Paz, Ami"https://www.zbmath.org/authors/?q=ai:paz.ami"Suomela, Jukka"https://www.zbmath.org/authors/?q=ai:suomela.jukkaSummary: In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the \textit{congested clique} model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an \(O(n^{1-2/\omega })\) round matrix multiplication algorithm, where \(\omega < 2.3728639\) is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include:
1. triangle and 4-cycle counting in \(O(n^{0.158})\) rounds, improving upon the \(O(n^{1/3})\) algorithm of
\textit{D. Dolev} et al. [Lect. Notes Comput. Sci. 7611, 195--209 (2012; Zbl 1377.68316)],
2. a \((1 + o(1))\)-approximation of all-pairs shortest paths in \(O(n^{0.158})\) rounds, improving upon the \(\tilde{O} (n^{1/2})\)-round \((2 + o(1))\)-approximation algorithm given by
\textit{D. Nanongkai} [in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC'14. New York, NY: Association for Computing Machinery (ACM). 565--573 (2014; Zbl 1315.05136)], and
3. computing the girth in \(O(n^{0.158})\) rounds, which is the first non-trivial solution in this model. In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles.A faster tree-decomposition based algorithm for counting linear extensions.https://www.zbmath.org/1452.682652021-02-12T15:23:00+00:00"Kangas, Kustaa"https://www.zbmath.org/authors/?q=ai:kangas.kustaa"Koivisto, Mikko"https://www.zbmath.org/authors/?q=ai:koivisto.mikko"Salonen, Sami"https://www.zbmath.org/authors/?q=ai:salonen.samiSummary: We investigate the problem of computing the number of linear extensions of a given \(n\)-element poset whose cover graph has treewidth \(t\). We present an algorithm that runs in time \(\tilde{O} (n^{t + 3})\) for any constant \(t\); the notation \(\tilde{O}\) hides polylogarithmic factors. Our algorithm applies dynamic programming along a tree decomposition of the cover graph; the join nodes of the tree decomposition are handled by fast multiplication of multivariate polynomials. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters \(n\) and \(t\) alone: fixing these parameters leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. We compare two approaches to select an efficient tree decomposition: one is to include additional features of the tree decomposition to build a more accurate, heuristic cost function; the other approach is to fit a statistical regression model to collected running time data. Both approaches are shown to yield a tree decomposition that typically is significantly more efficient than a random optimal-width tree decomposition.Randomized approximation scheme for Steiner multi cycle in the Euclidean plane.https://www.zbmath.org/1452.681382021-02-12T15:23:00+00:00"Lintzmayer, Carla N."https://www.zbmath.org/authors/?q=ai:lintzmayer.carla-negri"Miyazawa, Flávio K."https://www.zbmath.org/authors/?q=ai:miyazawa.flavio-keidi"Moura, Phablo F. S."https://www.zbmath.org/authors/?q=ai:moura.phablo-f-s"Xavier, Eduardo C."https://www.zbmath.org/authors/?q=ai:xavier.eduardo-candidoSummary: We propose a randomized approximation scheme for the Euclidean Steiner Multi Cycle problem which runs in quasilinear time. In this problem, we are given a set of \(n\) pairs of points (terminals) \(\mathcal{T} = \{ \{ t_i , t_i^\prime \} \}_{i = 1}^n\) in the Euclidean plane, and the objective is to find a collection of cycles of minimum cost such that \(t_i\) and \(t_i^\prime\) belong to a same cycle, for each \(i \in \{1, \ldots, n \} \). This problem extends the Steiner Cycle problem in the same way the Steiner Forest extends the Steiner Tree problem. Additionally, it has applications on routing problems with pickup and delivery locations.Semi-online machine covering on two hierarchical machines with known total size of low-hierarchy jobs.https://www.zbmath.org/1452.680312021-02-12T15:23:00+00:00"Xiao, Man"https://www.zbmath.org/authors/?q=ai:xiao.man"Wu, Gangxiong"https://www.zbmath.org/authors/?q=ai:wu.gangxiong"Li, Weidong"https://www.zbmath.org/authors/?q=ai:li.weidongSummary: In this paper, we consider the online machine covering problem on two hierarchical machines with known the total size of low-hierarchy. We present several best possible online algorithms when some addition information is known or a buffer is given.
For the entire collection see [Zbl 1423.68038].Dogson's rule and Yong's rule.https://www.zbmath.org/1452.911242021-02-12T15:23:00+00:00"Caragiannis, Ioannis"https://www.zbmath.org/authors/?q=ai:caragiannis.ioannis"Hemaspaandra, Edith"https://www.zbmath.org/authors/?q=ai:hemaspaandra.edith"Hemaspaandra, Lane A."https://www.zbmath.org/authors/?q=ai:hemaspaandra.lane-aSummary: Dodgson's and Young's election systems, dating from 1876 and 1977, are beautiful,
historically resonant election systems. Surprisingly, both of these systems turn out to
have highly intractable winner-determination problems: The winner problems of these
systems are complete for parallel access to NP. This chapter discusses both the complexity
of these winner-determination problems and approaches -- through heuristic
algorithms, fixed-parameter algorithms, and approximation algorithms -- to circumventing
that complexity.
For the entire collection see [Zbl 1436.91001].Special issue dedicated to the 13th international symposium on parameterized and exact computation.https://www.zbmath.org/1452.680122021-02-12T15:23:00+00:00"Paul, Christophe (ed.)"https://www.zbmath.org/authors/?q=ai:paul.christophe"Pilipczuk, Michał (ed.)"https://www.zbmath.org/authors/?q=ai:pilipczuk.michalFrom the text: We are pleased to present this special issue of Algorithmica to the 13th International Symposium on Parameterized and Exact Computation (IPEC) held in Helsinki, Finland. IPEC (formerly IWPEC) is a series of international symposia covering research in all aspects of parameterized and exact algorithms and complexity. Started in 2004 as a biennial workshop, it became an annual event in 2009 and is now a highly recognized annual meeting.Gathering in the plane of location-aware robots in the presence of spies.https://www.zbmath.org/1452.682392021-02-12T15:23:00+00:00"Czyzowicz, Jurek"https://www.zbmath.org/authors/?q=ai:czyzowicz.jurek"Killick, Ryan"https://www.zbmath.org/authors/?q=ai:killick.ryan"Kranakis, Evangelos"https://www.zbmath.org/authors/?q=ai:kranakis.evangelos"Krizanc, Danny"https://www.zbmath.org/authors/?q=ai:krizanc.danny"Morales-Ponce, Oscar"https://www.zbmath.org/authors/?q=ai:morales-ponce.oscarSummary: A set of mobile robots (represented as points) is distributed in the Cartesian plane. The collection contains an unknown subset of Byzantine robots which are indistinguishable from the reliable ones. The reliable robots need to gather, i.e., arrive to a configuration in which at the same time, all of them occupy the same point on the plane. The robots are equipped with GPS devices and at the beginning of the gathering process they communicate the Cartesian coordinates of their respective positions to a central authority. On the basis of this information, and without the knowledge of which robots are faulty, the central authority designs a trajectory for every robot. The central authority aims to provide the trajectories which result in the shortest possible gathering time of the reliable robots. The efficiency of a gathering strategy is measured by its competitive ratio, i.e., the maximal ratio between the time required for gathering achieved by the given trajectories and the optimal time required for gathering in the offline case, i.e., when the faulty robots are known to the central authority in advance. The role of the Byzantine robots, controlled by the adversary, is to act so that the gathering is delayed and the resulting competitive ratio is maximized.
The objective of our paper is to propose efficient algorithms when the central authority is aware of an upper bound on the number of Byzantine robots. We give optimal algorithms for collections of robots known to contain at most one faulty robot. When the proportion of Byzantine robots is known to be less than one half or one third, we provide algorithms with small constant competitive ratios. We also propose algorithms with bounded competitive ratio in the case where the proportion of faulty robots is arbitrary.A method to compute the sparse graphs for traveling salesman problem based on frequency quadrilaterals.https://www.zbmath.org/1452.902802021-02-12T15:23:00+00:00"Wang, Yong"https://www.zbmath.org/authors/?q=ai:wang.yong.1|wang.yong.10|wang.yong.8|wang.yong.9|wang.yong.6|wang.yong.3|wang.yong|wang.yong.2|wang.yong.5|wang.yong.7"Remmel, Jeffrey"https://www.zbmath.org/authors/?q=ai:remmel.jeffrey-bSummary: In this paper, an iterative algorithm is designed to compute the sparse graphs for traveling salesman problem (\textit{TSP}) according to the frequency quadrilaterals so that the computation time of the algorithms for \textit{TSP} will be lowered. At each computation cycle, the algorithm first computes the average frequency \(\overline{f} (e)\) of an edge \(e\) with \(N\) frequency quadrilaterals containing \(e\) in the input graph \(G(V, E)\). Then the \(1/3|E|\) edges with low frequency are eliminated to generate the output graph with a smaller number of edges. The algorithm can be iterated several times and the original optimal Hamiltonian cycle is preserved with a high probability. The experiments demonstrate the algorithm computes the sparse graphs with the \(O(n \log_{2}n)\) edges containing the original optimal Hamiltonian cycle for most of the \textit{TSP} instances in the \textit{TSPLIB}. The computation time of the iterative algorithm is \(O(\textit{Nn}^2)\).
For the entire collection see [Zbl 1408.68012].Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs.https://www.zbmath.org/1452.681392021-02-12T15:23:00+00:00"Liu, Pengcheng"https://www.zbmath.org/authors/?q=ai:liu.pengcheng"Zhang, Zhao"https://www.zbmath.org/authors/?q=ai:zhang.zhao"Huang, Xiaohui"https://www.zbmath.org/authors/?q=ai:huang.xiaohuiSummary: In this paper, we study the minimum (connected) \(k\)-bounded-degree node deletion problem (Min\((C)k\)BDND). For a connected graph \(G\), a constant \(k\) and a weight function \(w : V \to \mathbb{R}^+\), a vertex set \(C \subseteq V(G)\) is a \(k\) BDND-set if the maximum degree of graph \(G - C\) is at most \(k\). If furthermore, the subgraph of \(G\) induced by \(C\) is connected, then \(C\) is a \(Ck\) BDND-set. The goal of MinW\(k\)BDND (resp. MinWC\(k\)BDND) is to find a \(k\)BDND-set (resp. \(Ck\)BDND-set) with the minimum weight. In this paper, we focus on their cardinality versions with \(w(v) \equiv 1\), \(v \in V\), which are denoted as Min\(k\)BDND and MinC\(k\)BDND. This paper presents a \((1 + \varepsilon)\) and a 3.76-approximation algorithm for Min\(k\)BDND and MinC\(k\)BDND on unit disk graphs, respectively, where \(0 < \varepsilon < 1\) is an arbitrary constant.Delivery route optimization with automated vehicle in smart urban environment.https://www.zbmath.org/1452.900662021-02-12T15:23:00+00:00"Luo, Chuanwen"https://www.zbmath.org/authors/?q=ai:luo.chuanwen"Li, Deying"https://www.zbmath.org/authors/?q=ai:li.deying"Ding, Xingjian"https://www.zbmath.org/authors/?q=ai:ding.xingjian"Wu, Weili"https://www.zbmath.org/authors/?q=ai:wu.weiliSummary: As a part of the smart urban construction, automated driving is introduced to improve the utilization efficiency of cars and roads, which not only reduces the incidence of traffic accidents, but also improves the environment quality. With the development of the smart urban, it is predictable that, in the city of the future, the service of package pickup and delivery or takeout will be supported mainly by automated vehicles. However, the existing works mainly focus on the variants of the Vehicle Routing Problem (VRP), in which they either take no account of service time of automated vehicle for customers when the automated vehicle arrives at the locations of customers or ignore the impact of rewards gained from customers on path planning of the automated vehicles. In this paper, we also extend a variant of VRP where an automated vehicle is used to package delivery or distribution of food in the smart urban environment, which is called the Delivery Reward Maximization (DRM) problem. The problem aims at designing a route of the automated vehicle while considering the service time for customers before their deadlines and the impact of rewards of the automated vehicle on path planning. We first prove that the DRM problem is NP-hard. Then we study two special cases of the DRM problem, which are called Linear DRM (LDRM) problem and Two-dimensional DRM (TDRM) problem, respectively. In the LDRM and TDRM problems, all customers have the same visiting deadlines and are deployed on the one-dimensional line and two-dimensional plane, respectively. Then we prove that the LDRM and TDRM problems are also NP-hard and propose a constant approximation algorithm for each of them. Afterward, we propose a greedy algorithm to solve the DRM problem, and give the analysis by counterexample.Minimizing ESCT forms for two-variable multiple-valued input binary output functions.https://www.zbmath.org/1452.941392021-02-12T15:23:00+00:00"Mizuki, Takaaki"https://www.zbmath.org/authors/?q=ai:mizuki.takaaki"Mikami, Daizo"https://www.zbmath.org/authors/?q=ai:mikami.daizo"Sone, Hideaki"https://www.zbmath.org/authors/?q=ai:sone.hideakiSummary: As EXOR (Exclusive-OR) expansions of binary output functions, the ESOP (EXOR Sum of Products) form and its extension, the ESCT (EXOR Sum of Complex Terms) form, have been studied extensively in the literature. An efficient algorithm for minimizing ESOP forms is known for two-variable multiple-valued input functions. On the other hand, no ESCT minimization algorithm is known for such functions. In this paper, we give an efficient algorithm for minimizing ESCT forms of two-variable multiple-valued input functions, showing that the number of terms can be reduced by at most one.Group sweep coverage with guaranteed approximation ratio.https://www.zbmath.org/1452.680292021-02-12T15:23:00+00:00"Liu, Chuang"https://www.zbmath.org/authors/?q=ai:liu.chuang"Du, Hongwei"https://www.zbmath.org/authors/?q=ai:du.hongwei"Ye, Qiang"https://www.zbmath.org/authors/?q=ai:ye.qiang"Xu, Wen"https://www.zbmath.org/authors/?q=ai:xu.wenSummary: Wireless Sensor Networks (WSNs) are often deployed to monitor a region of interest. With sweep coverage, mobile sensor nodes are scheduled to move along a planned route (i.e. sweep route) in order to collect the data from a series of Point of Interests (POIs) sequentially. In this paper, we generalize the sweep coverage problem by proposing a new coverage paradigm, group sweep coverage. With group sweep coverage, the POIs are divided into several groups. A group is said to be covered when one of the POIs in the group is covered. The goal in group sweep coverage is to construct a sweep route that mobile sensor nodes should follow in order to cover all groups during each predefined period. In our research, we devised two algorithms for group sweep coverage: AGSC and DSRM. AGSC is a centralized scheme whose approximation ratio is \(5 \Delta\). Namely, the length of the sweep route generated by AGSC is at most \(5 \Delta\) times that of the optimal sweep route. DSRM is a distributed scheme for large-scale networks with dynamic POIs. Compared with AGSC, DSRM leads to the same approximation ratio and better scalability. Our experimental results indicate that both AGSC and DSRM outperform the state-of-the-art schemes in terms of average and maximal sweep route length.Algorithms for visualizing phylogenetic networks.https://www.zbmath.org/1452.681422021-02-12T15:23:00+00:00"Tollis, Ioannis G."https://www.zbmath.org/authors/?q=ai:tollis.ioannis-g"Kakoulis, Konstantinos G."https://www.zbmath.org/authors/?q=ai:kakoulis.konstantinos-gSummary: We study the problem of visualizing phylogenetic networks, which are extensions of the Tree of Life in biology. We use a space filling visualization method, called DAGmaps, in order to obtain clear visualizations using limited space. In this paper, we first show that the general problem of drawing galled networks as DAGmaps is NP-complete. Next, we restrict our attention to galled trees and planar galled networks and present linear time algorithms for visualizing them as DAGmaps. Finally, we explore whether these graphs can be visualized using One-Dimensional DAGmaps.FANCFIS: fast adaptive neuro-complex fuzzy inference system.https://www.zbmath.org/1452.681642021-02-12T15:23:00+00:00"Yazdanbakhsh, Omolbanin"https://www.zbmath.org/authors/?q=ai:yazdanbakhsh.omolbanin"Dick, Scott"https://www.zbmath.org/authors/?q=ai:dick.scottSummary: Large-scale multivariate time series forecasting is an increasingly important problem, with sensor networks pouring out sampled data at unprecedented rates, trillions of dollar's worth of stock trades made every data, and zettabytes of traffic transmitted over the Internet every year. While they are only examples of the much larger domain of general data streams, the uniformly-sampled time series still remains a very large and important subdomain. Extensive research has shown that machine-learning algorithms can often be very effective forecasting models, but many of these algorithms do not scale well. The Adaptive Neuro-Complex-Fuzzy Inferential System is one such approach; built to leverage complex fuzzy sets, it is both an accurate and parsimonious forecasting algorithm. However, its scaling is poor due to a relatively slow training algorithm (gradient descent hybridized with chaotic simulated annealing). Before the algorithm can be used for large-scale forecasting, a fast training algorithm that preserves the system's accuracy and compactness must be developed.
We propose the Fast Adaptive Neuro-Complex Fuzzy Inference System, which is designed for fast training of a compact, accurate forecasting model. We use the Fast Fourier Transform algorithm to identify the dominant frequencies in a time series, and then create complex fuzzy sets to match them as the antecedents of complex fuzzy rules. Consequent linear functions are then learned via recursive least-squares. We evaluate this algorithm on both univariate and multivariate time series, finding that this incremental-learning algorithm is as accurate and compact as its slower predecessor, and can be trained much more quickly.Fully dynamic arboricity maintenance.https://www.zbmath.org/1452.681302021-02-12T15:23:00+00:00"Banerjee, Niranka"https://www.zbmath.org/authors/?q=ai:banerjee.niranka"Raman, Venkatesh"https://www.zbmath.org/authors/?q=ai:raman.venkatesh"Saurabh, Saket"https://www.zbmath.org/authors/?q=ai:saurabh.saketThe arboricity of a graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges is defined as the minimum number of edge-disjoint forests that the edges of the graph can be partitioned into. The exact arboricity can be determined in \(O(m^{3/2}\log(n^2/m))\) time and 2-approximation in \(O(m+n)\) time. There is also an \((1+\epsilon)\)-approximation scheme that requires \(O(m\log n\log\tau \epsilon^{-1})\) time, where \(\tau\) is the arboricity of graph \(G\).
This paper focuses on the dynamic graph algorithms. If edges are inserted or deleted over time, a dynamic algorithm maintains some additional graph information which is then used to calculate graph arboricity faster than a static algorithm that starts from scratch. The algorithm presented in the paper maintains a decomposition into \(\tau\) edge-disjoint spanning forests and both insertion and deletion take \(O(m\log n)\) time in the worst case. The paper concludes with an amortized bound of \(\Omega(\log n)\) for the cost of answering the arboricity query under edge insertions and deletions.
Reviewer: Vladimír Lacko (Košice)Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics.https://www.zbmath.org/1452.682742021-02-12T15:23:00+00:00"Chan, T.-H. Hubert"https://www.zbmath.org/authors/?q=ai:chan.t-h-hubert"Jiang, Shaofeng H.-C."https://www.zbmath.org/authors/?q=ai:jiang.shaofeng-h-cComputing nearby non-trivial Smith forms.https://www.zbmath.org/1452.650842021-02-12T15:23:00+00:00"Giesbrecht, Mark"https://www.zbmath.org/authors/?q=ai:giesbrecht.mark-w"Haraldson, Joseph"https://www.zbmath.org/authors/?q=ai:haraldson.joseph"Labahn, George"https://www.zbmath.org/authors/?q=ai:labahn.georgeSummary: We consider the problem of computing the nearest matrix polynomial with a non-trivial Smith Normal Form. We show that computing the Smith form of a matrix polynomial is amenable to numeric computation as an optimization problem. Furthermore, we describe an effective optimization technique to find a nearby matrix polynomial with a non-trivial Smith form. The results are then generalized to include the computation of a matrix polynomial having a maximum specified number of ones in the Smith Form (i.e., with a maximum specified McCoy rank).
We discuss the geometry and existence of solutions and how our results can be used for an error analysis. We develop an optimization-based approach and demonstrate an iterative numerical method for computing a nearby matrix polynomial with the desired spectral properties. We also describe an implementation of our algorithms and demonstrate the robustness with examples in Maple.Generation techniques for linear programming instances with controllable properties.https://www.zbmath.org/1452.902142021-02-12T15:23:00+00:00"Bowly, Simon"https://www.zbmath.org/authors/?q=ai:bowly.simon"Smith-Miles, Kate"https://www.zbmath.org/authors/?q=ai:smith-miles.kate-a"Baatar, Davaatseren"https://www.zbmath.org/authors/?q=ai:baatar.davaatseren"Mittelmann, Hans"https://www.zbmath.org/authors/?q=ai:mittelmann.hans-detlefSummary: This paper addresses the problem of generating synthetic test cases for experimentation in linear programming. We propose a method which maps instance generation and instance space search to an alternative encoded space. This allows us to develop a generator for feasible bounded linear programming instances with controllable properties. We show that this method is capable of generating any feasible bounded linear program, and that parameterised generators and search algorithms using this approach generate only feasible bounded instances. Our results demonstrate that controlled generation and instance space search using this method achieves feature diversity more effectively than using a direct representation.Simple optimal hitting sets for small-success RL.https://www.zbmath.org/1452.682712021-02-12T15:23:00+00:00"Hoza, William M."https://www.zbmath.org/authors/?q=ai:hoza.william-m"Zuckerman, David"https://www.zbmath.org/authors/?q=ai:zuckerman.davidFrom gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more.https://www.zbmath.org/1452.680832021-02-12T15:23:00+00:00"Chalermsook, Parinya"https://www.zbmath.org/authors/?q=ai:chalermsook.parinya"Cygan, Marek"https://www.zbmath.org/authors/?q=ai:cygan.marek"Kortsarz, Guy"https://www.zbmath.org/authors/?q=ai:kortsarz.guy"Laekhanukit, Bundit"https://www.zbmath.org/authors/?q=ai:laekhanukit.bundit"Manurangsi, Pasin"https://www.zbmath.org/authors/?q=ai:manurangsi.pasin"Nanongkai, Danupon"https://www.zbmath.org/authors/?q=ai:nanongkai.danupon"Trevisan, Luca"https://www.zbmath.org/authors/?q=ai:trevisan.lucaOn approximating the number of \(k\)-cliques in sublinear time.https://www.zbmath.org/1452.682762021-02-12T15:23:00+00:00"Eden, Talya"https://www.zbmath.org/authors/?q=ai:eden.talya"Ron, Dana"https://www.zbmath.org/authors/?q=ai:ron.dana"Seshadhri, C."https://www.zbmath.org/authors/?q=ai:seshadhri.comandurColor-to-gray conversion with perceptual preservation and dark channel prior.https://www.zbmath.org/1452.651102021-02-12T15:23:00+00:00"Liu, Jun"https://www.zbmath.org/authors/?q=ai:liu.jun.3|liu.jun.5|liu.jun.1|liu.jun.4|liu.jun|liu.jun.2"Fang, Faming"https://www.zbmath.org/authors/?q=ai:fang.faming"Du, Ning"https://www.zbmath.org/authors/?q=ai:du.ningSummary: This paper aims to present a decolorization strategy based on perceptual consistency and dark channel prior. The proposed model consists of effective fidelity terms and a prior term. We use the \(\ell_0\)-norm to control the sparsity of the dark channel prior. To solve the non-convex minimization problem, we employ the split and penalty technique to simplify the minimization problem and then solve it by the carefully designed iteration scheme.Besides, we show the convergence of the algorithm using Kurdyka-Łojasiewicz property. The numerical evaluation in comparison with other state-of-the-art methods demonstrates the effectiveness of the proposed method.Robust algorithms with polynomial loss for near-unanimity CSPs.https://www.zbmath.org/1452.680872021-02-12T15:23:00+00:00"Dalmau, Víctor"https://www.zbmath.org/authors/?q=ai:dalmau.victor"Kozik, Marcin"https://www.zbmath.org/authors/?q=ai:kozik.marcin"Krokhin, Andrei"https://www.zbmath.org/authors/?q=ai:krokhin.andrei-a"Makarychev, Konstantin"https://www.zbmath.org/authors/?q=ai:makarychev.konstantin-s"Makarychev, Yury"https://www.zbmath.org/authors/?q=ai:makarychev.yury-s"Opršal, Jakub"https://www.zbmath.org/authors/?q=ai:oprsal.jakubCoordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch.https://www.zbmath.org/1452.682402021-02-12T15:23:00+00:00"Demaine, Erik D."https://www.zbmath.org/authors/?q=ai:demaine.erik-d"Fekete, Sándor P."https://www.zbmath.org/authors/?q=ai:fekete.sandor-p"Keldenich, Phillip"https://www.zbmath.org/authors/?q=ai:keldenich.phillip"Meijer, Henk"https://www.zbmath.org/authors/?q=ai:meijer.henk-g"Scheffer, Christian"https://www.zbmath.org/authors/?q=ai:scheffer.christianThe power of verification for greedy mechanism design.https://www.zbmath.org/1452.910712021-02-12T15:23:00+00:00"Fotakis, Dimitris"https://www.zbmath.org/authors/?q=ai:fotakis.dimitris-a"Krysta, Piotr"https://www.zbmath.org/authors/?q=ai:krysta.piotr"Ventre, Carmine"https://www.zbmath.org/authors/?q=ai:ventre.carmineSummary: Greedy algorithms are known to provide, in polynomial time, near optimal approximation guarantees for combinatorial auctions (CAs) with multidimensional bidders. It is known that truthful greedy-like mechanisms for CAs with multi-minded bidders do not achieve good approximation guarantees. In this work, we seek a deeper understanding of greedy mechanism design and investigate under which general assumptions, we can have efficient and truthful greedy mechanisms for CAs. Towards this goal, we use the framework of priority algorithms and weak and strong verification, where the bidders are not allowed to overbid on their winning set or on any subset of this set, respectively. We provide a complete characterization of the power of weak verification showing that it is sufficient and necessary for any greedy fixed priority algorithm to become truthful with the use of money or not, depending on the ordering of the bids. Moreover, we show that strong verification is sufficient and necessary to obtain a 2-approximate truthful mechanism with money, based on a known greedy algorithm, for the problem of submodular CAs in finite bidding domains. Our proof is based on an interesting structural analysis of the strongly connected components of the declaration graph.Counting thin subgraphs via packings faster than meet-in-the-middle time.https://www.zbmath.org/1452.681332021-02-12T15:23:00+00:00"Björklund, Andreas"https://www.zbmath.org/authors/?q=ai:bjorklund.andreas"Kaski, Petteri"https://www.zbmath.org/authors/?q=ai:kaski.petteri"Kowalik, Łukasz"https://www.zbmath.org/authors/?q=ai:kowalik.lukaszA pseudo-quasi-polynomial algorithm for mean-payoff parity games.https://www.zbmath.org/1452.910532021-02-12T15:23:00+00:00"Daviaud, Laure"https://www.zbmath.org/authors/?q=ai:daviaud.laure"Jurdziński, Martin"https://www.zbmath.org/authors/?q=ai:jurdzinski.martin"Lazić, Ranko"https://www.zbmath.org/authors/?q=ai:lazic.rankoSpecial issue on the international conference on algorithmic aspects in information and management 2019 (AAIM'19).https://www.zbmath.org/1452.680142021-02-12T15:23:00+00:00"Sun, Xiaoming (ed.)"https://www.zbmath.org/authors/?q=ai:sun.xiaoming"Zhang, Jialin (ed.)"https://www.zbmath.org/authors/?q=ai:zhang.jialinFrom the text: This special issue of Theoretical Computer Science consists of 8 selected papers. They were presented in the 13th International Conference on Algorithmic Aspects in Information and Management (AAIM 2019), held on August 6--8, 2019, in Beijing, China. AAIM 2019 aims to stimulate the various fields for which algorithmics has become a crucial enabler, and to strengthen the ties between the Eastern and Western research communities of algorithmics and applications. The conference accepted 31 regular papers out of \(\sim 50\) full submission. 12 of them are selected and invited to submit the extended versions to this special issue and finally 81 of them are accepted through a regular reviewing process.Max-sum diversification, monotone submodular functions, and dynamic updates.https://www.zbmath.org/1452.682732021-02-12T15:23:00+00:00"Borodin, Allan"https://www.zbmath.org/authors/?q=ai:borodin.allan-b"Jain, Aadhar"https://www.zbmath.org/authors/?q=ai:jain.aadhar"Lee, Hyun Chul"https://www.zbmath.org/authors/?q=ai:lee.hyunchul"Ye, Yuli"https://www.zbmath.org/authors/?q=ai:ye.yuliImproved approximation algorithm for Steiner \(k\)-forest with nearly uniform weights.https://www.zbmath.org/1452.682752021-02-12T15:23:00+00:00"Dinitz, Michael"https://www.zbmath.org/authors/?q=ai:dinitz.michael-h"Kortsarz, Guy"https://www.zbmath.org/authors/?q=ai:kortsarz.guy"Nutov, Zeev"https://www.zbmath.org/authors/?q=ai:nutov.zeevProceedings of the 23rd symposium on algorithm engineering and experiments, ALENEX '21, virtual event, January 10--11, 2021.https://www.zbmath.org/1452.680082021-02-12T15:23:00+00:00"Farach-Colton, Martin (ed.)"https://www.zbmath.org/authors/?q=ai:farach-colton.martin"Storandt, Sabine (ed.)"https://www.zbmath.org/authors/?q=ai:storandt.sabineFrom the publisher's description: The 23rd meeting on algorithm engineering and experiments (ALENEX 21) was originally scheduled to take place in Arlington, VA, on January 10--11, 2021, but then had to be turned into a virtual meeting due to the pandemic.
ALENEX 21 was supported by SIAM, the Society for Industrial and Applied Mathematics. ALENEX 21, APOCS 21 and SOSA 21 took place in conjunction with SODA 21, the 32nd ACM-SIAM Symposium on Discrete Algorithms, and were incorporated as separate tracks in the SODA program.
The articles of mathematical interest will be reviewed individually. For the preceding symposium see [Zbl 1434.68019].
Indexed articles:
\textit{Popp, Merten; Schlag, Sebastian; Schulz, Christian; Seemaier, Daniel}, Multilevel acyclic hypergraph partitioning, 1-15 [Zbl 07302433]
\textit{Gottesbüren, Lars; Heuer, Tobias; Sanders, Peter; Schlag, Sebastian}, Scalable shared-memory hypergraph partitioning, 16-30 [Zbl 07302434]
\textit{Wheatman, Brian; Xu, Helen}, A parallel packed memory array to store dynamic graphs, 31-45 [Zbl 07302435]
\textit{Boffa, Antonio; Ferragina, Paolo; Vinciguerra, Giorgio}, A ``learned'' approach to quicken and compress rank/select dictionaries, 46-59 [Zbl 07302436]
\textit{Boucher, Christina; Cvacho, Ondřej; Gagie, Travis; Holub, Jan; Manzini, Giovanni; Navarro, Gonzalo; Rossi, Massimiliano}, PFP compressed suffix trees, 60-72 [Zbl 07302437]
\textit{Anders, Markus; Schweitzer, Pascal}, Engineering a fast probabilistic isomorphism test, 73-84 [Zbl 07302438]
\textit{Georgiadis, Loukas; Kefallinos, Dionysios; Laura, Luigi; Parotsidis, Nikos}, An experimental study of algorithms for computing the edge connectivity of a directed graph, 85-97 [Zbl 07302439]
\textit{Buchhold, Valentin; Sanders, Peter; Wagner, Dorothea}, Fast, exact and scalable dynamic ridesharing, 98-112 [Zbl 07302440]
\textit{Ost, Wolfgang; Schulz, Christian; Strash, Darren}, Engineering data reduction for nested dissection, 113-127 [Zbl 07302441]
\textit{Gellner, Alexander; Lamm, Sebastian; Schulz, Christian; Strash, Darren; Zaválnij, Bogdán}, Boosting data reduction for the maximum weight independent set problem using increasing transformations, 128-142 [Zbl 07302442]
\textit{Goranci, Gramoz; Henzinger, Monika; Leniowski, Dariusz; Schulz, Christian; Svozil, Alexander}, Fully dynamic \(k\)-center clustering in low dimensional metrics, 143-153 [Zbl 07302443]
\textit{Angriman, Eugenio; Becker, Ruben; D'angelo, Gianlorenzo; Gilbert, Hugo; van der Grinten, Alexander; Meyerhenke, Henning}, Group-harmonic and group-closeness maximization -- approximation and engineering, 154-168 [Zbl 07302444]
\textit{Plachetta, Rick; van der Grinten, Alexander}, SAT-and-reduce for vertex cover: accelerating branch-and-reduce by SAT solving, 169-180 [Zbl 07302445]
\textit{Barlow, Michael; Konrad, Christian; Nandasena, Charana}, Streaming set cover in practice, 181-192 [Zbl 07302446]
\textit{Maria, Clément; Rouillé, Owen}, Computation of large asymptotics of 3-manifold quantum invariants, 193-206 [Zbl 07302447]
\textit{Kerber, Michael; Rolle, Alexander}, Fast minimal presentations of bi-graded persistence modules, 207-220 [Zbl 07302448]Decomposing octilinear polygons into triangles and rectangles.https://www.zbmath.org/1452.682452021-02-12T15:23:00+00:00"Cicerone, Serafino"https://www.zbmath.org/authors/?q=ai:cicerone.serafino"Di Stefano, Gabriele"https://www.zbmath.org/authors/?q=ai:di-stefano.gabrieleSummary: In this paper, we study the minimal decomposition of octilinear polygons with holes into octilinear triangles and rectangles. This new problem is relevant in the context of modern electronic CAD systems, where it arises when the generation and propagation of electromagnetic noise into multi-layer PCBs has to be detected. It can be seen as a generalization of a problem deeply investigated in the last decades: the minimal decomposition of rectilinear polygons into rectangles, which is solvable in polynomial time. We show that the new problem is NP-hard. We also show the NP-hardness of a related problem, that is the decomposition of an octilinear polygon with holes into octilinear convex polygons. For both problems, we propose efficient approximation algorithms.
For the entire collection see [Zbl 1318.68008].The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm.https://www.zbmath.org/1452.903092021-02-12T15:23:00+00:00"Cheriyan, J."https://www.zbmath.org/authors/?q=ai:cheriyan.joseph"Dippel, J."https://www.zbmath.org/authors/?q=ai:dippel.j"Grandoni, F."https://www.zbmath.org/authors/?q=ai:grandoni.fabrizio"Khan, A."https://www.zbmath.org/authors/?q=ai:khan.arindam"Narayan, V. V."https://www.zbmath.org/authors/?q=ai:narayan.vishnu-vSummary: We present a \(\frac{7}{4}\) approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any given MAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a \(\frac{7}{4}\) approximation algorithm for a well-structured MAP instance. The algorithm starts with a min-cost 2-edge cover and then applies ear-augmentation steps. We analyze the cost of the ear-augmentations using an approach similar to the one proposed by
\textit{S. Vempala} and \textit{A. Vetta} for the (unweighted) min-size 2-ECSS problem [Lect. Notes Comput. Sci. 1913, 262--273 (2000; Zbl 0976.90114)].Partitioning a graph into small pieces with applications to path transversal.https://www.zbmath.org/1452.681372021-02-12T15:23:00+00:00"Lee, Euiwoong"https://www.zbmath.org/authors/?q=ai:lee.euiwoongSummary: Given a graph \(G = (V, E)\) and an integer \(k \in \mathbb{N}\), we study \(k\)-\textsc{Vertex Separator} (resp. \(k\)-\textsc{Edge Separator}), where the goal is to remove the minimum number of vertices (resp. edges) such that each connected component in the resulting graph has less than \(k\) vertices. We also study \(k\)-\textsc{Path Transversal}, where the goal is to remove the minimum number of vertices such that there is no simple path of length \(k\). Our main results are the following improved approximation algorithms.\begin{itemize} \item[--] \(O(\log k)\)-approximation algorithm for \(k\)-\textsc{Vertex Separator} that runs in time \(2^{O(k)} n + n^{O(1)}\). It improves the simple \(k\)-approximation, and runs faster than the lower bound \(k^{\varOmega (\mathsf{OPT})} n^{\varOmega (1)}\) for exact algorithms assuming the exponential time hypothesis (ETH) when \(\mathsf{OPT}> k\). We also prove that there is no \(n^{(1/\log \log n)^c}\)-approximation algorithm that runs in time \(\operatorname{poly}(n, k)\) assuming the ETH. \item[--] \(O(\log k)\)-approximation algorithm for \(k\)-\textsc{Edge Separator} that runs in time \(n^{O(1)}\). It improves the best previous graph partitioning algorithm for small \(k = n^{o(1)}\). \item[--] \(O(\log k)\)-approximation algorithm for \(k\)-\textsc{Path Transversal} that runs in time \(n^{O(1)} + 2^{O(k^3 \log k)} n^{2} \log n\). Previously, the existence of an \((1 - \delta )k\)-approximation algorithm for fixed \(\delta > 0\) (even using \(n^{f(k)}\) time) was open. \end{itemize}Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks.https://www.zbmath.org/1452.682692021-02-12T15:23:00+00:00"Henzinger, Monika"https://www.zbmath.org/authors/?q=ai:rauch-henzinger.monika"Krinninger, Sebastian"https://www.zbmath.org/authors/?q=ai:krinninger.sebastian"Nanongkai, Danupon"https://www.zbmath.org/authors/?q=ai:nanongkai.danuponOn abelian longest common factor with and without RLE.https://www.zbmath.org/1452.682802021-02-12T15:23:00+00:00"Grabowski, Szymon"https://www.zbmath.org/authors/?q=ai:grabowski.szymon"Kociumaka, Tomasz"https://www.zbmath.org/authors/?q=ai:kociumaka.tomasz"Radoszewski, Jakub"https://www.zbmath.org/authors/?q=ai:radoszewski.jakubSummary: We consider the abelian longest common factor problem in two scenarios: when input strings are uncompressed and are of length at most \(n\), and when the input strings are run-length encoded and their compressed representations have size at most \(m\). The alphabet size is denoted by \({\sigma}\). For the uncompressed problem, we show an \(O (n^2 / \log^{1+1/\sigma}n)\)-time and \(\mathcal{O}(n)\)-space algorithm in the case of \(\sigma = \mathcal{O}(1)\), making a non-trivial use of tabulation. For the RLE-compressed problem, we show two algorithms: one working in \(\mathcal{O}(m^2 \sigma^2 \log^3 m )\) time and \(\mathcal{O}(m (\sigma^2 +\log^2 m ))\) space, which employs line sweep, and one that works in \(\mathcal{O}(m^3)\) time and \(\mathcal{O}(m)\) space that applies in a careful way a sliding-window-based approach. The latter improves upon the previously known \(\mathcal{O}(nm^2)\)-time and \(\mathcal{O}(m^4 )\)-time algorithms that were recently developed by
\textit{S. Sugimoto} et al. [Lect. Notes Comput. Sci. 10765, 420--431 (2018; Zbl 06890136)] and
the first author [Lect. Notes Comput. Sci. 10508, 208--213 (2017; Zbl 07310998)],
respectively.Fast monotone summation over disjoint sets.https://www.zbmath.org/1452.680882021-02-12T15:23:00+00:00"Kaski, Petteri"https://www.zbmath.org/authors/?q=ai:kaski.petteri"Koivisto, Mikko"https://www.zbmath.org/authors/?q=ai:koivisto.mikko"Korhonen, Janne H."https://www.zbmath.org/authors/?q=ai:korhonen.janne-h"Sergeev, Igor S."https://www.zbmath.org/authors/?q=ai:sergeev.igor-sergeevichSummary: We study evaluation of sums indexed by input sets that are disjoint from output sets. For indices over all small subsets, we show a near-linear monotone complexity. Applications include counting maximum-weight paths and rectangular matrix permanents.Cryptomorphic topological structures: a computational, relation-algebraic approach.https://www.zbmath.org/1452.031392021-02-12T15:23:00+00:00"Berghammer, Rudolf"https://www.zbmath.org/authors/?q=ai:berghammer.rudolf"Schmidt, Gunther"https://www.zbmath.org/authors/?q=ai:schmidt.gunther.1"Winter, Michael"https://www.zbmath.org/authors/?q=ai:winter.michaelSummary: In this paper we present an approach to pointless topology that is based on the study of the \textit{membership} or \textit{is-element-of} relation within a typed or categorical version of the component-free calculus of relations. This allows us to study several other approaches to topology, including point-set topology, on an abstract and component-free level. In particular, we will show that topologies defined by open sets, closed sets, a family of neighbourhood systems, a topological kernel-mapping, a Kuratowski closure-mapping, or a topological Aumann contact relation are cryptomorphic concepts, i.e., each concept can bijectively be transformed into any other of these concepts. All transformations are specified via relation-algebraic expressions which, in case of set-theoretic relations (that is, in case of point-set topology) can immediately be executed by the specific purpose computer algebra system \textsc{RelView}.Efficient generation of shortest addition-multiplication chains.https://www.zbmath.org/1452.682812021-02-12T15:23:00+00:00"Bahig, Hatem M."https://www.zbmath.org/authors/?q=ai:bahig.hatem-m"Mahran, A. E. A."https://www.zbmath.org/authors/?q=ai:mahran.a-e-aSummary: The aim of this paper is to generalize some results on addition chains to addition-multiplication chains. The paper is concerned with generating shortest addition-multiplication chains. It first presents two methods for generating short addition-multiplication chains. Second, it presents an algorithm for generating a shortest addition-multiplication chain. Then it proposes three main improvements for generating a shortest addition-multiplication chain. The practical results show that the proposed improvements reduce, on the average, the running time and storage of the algorithm by about addition-multiplication chains. Finally, the paper discusses how to apply the algorithm to obtain some results that have been uncovered previously.Spectral norm of a symmetric tensor and its computation.https://www.zbmath.org/1452.150132021-02-12T15:23:00+00:00"Friedland, Shmuel"https://www.zbmath.org/authors/?q=ai:friedland.shmuel"Wang, Li"https://www.zbmath.org/authors/?q=ai:wang.li.4|wang.li.5|wang.li.6|wang.li.3|wang.li.1|wang.li|wang.li.2Summary: We show that the spectral norm of a \(d\)-mode real or complex symmetric tensor in \(n\) variables can be computed by finding the fixed points of the corresponding polynomial map. For a generic complex symmetric tensor the number of fixed points is finite, and we give upper and lower bounds for the number of fixed points. For \(n = 2\) we show that these fixed points are the roots of a corresponding univariate polynomial of degree at most \((d-1)^2 + 1\), except certain cases, which are completely analyzed. In particular, for \(n = 2\) the spectral norm of \(d\)-symmetric tensor is polynomially computable in \(d\) with a given relative precision. For a fixed \(n > 2\) we show that the spectral norm of a \(d\)-mode symmetric tensor is polynomially computable in \(d\) with a given relative precision with respect to the Hilbert-Schmidt norm of the tensor. These results show that the geometric measure of entanglement of \(d\)-mode symmetric qunits on \(\mathbb{C}^n\) are polynomially computable for a fixed \(n\).Randomized proof-labeling schemes.https://www.zbmath.org/1452.680242021-02-12T15:23:00+00:00"Fraigniaud, Pierre"https://www.zbmath.org/authors/?q=ai:fraigniaud.pierre"Patt-Shamir, Boaz"https://www.zbmath.org/authors/?q=ai:patt-shamir.boaz"Perry, Mor"https://www.zbmath.org/authors/?q=ai:perry.morSummary: Proof-labeling schemes, introduced
by \textit{A. Korman} et al. [Distrib. Comput. 22, No. 4, 215--233 (2010; Zbl 1267.68061)], are a mechanism to certify that a network configuration satisfies a given Boolean predicate. Such mechanisms find applications in many contexts, e.g., the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, predicate verification consists of neighbors exchanging labels, whose contents depends on the predicate. In this paper, we introduce the notion of \textit{randomized} proof-labeling schemes where messages are randomized and correctness is probabilistic. We show that randomization reduces verification complexity exponentially while guaranteeing probability of correctness arbitrarily close to one. We also present a novel message-size lower bound technique that applies to deterministic as well as randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of MST, acyclicity, connectivity, and longest cycle size.Noisy rumor spreading and plurality consensus.https://www.zbmath.org/1452.680232021-02-12T15:23:00+00:00"Fraigniaud, Pierre"https://www.zbmath.org/authors/?q=ai:fraigniaud.pierre"Natale, Emanuele"https://www.zbmath.org/authors/?q=ai:natale.emanueleSummary: Error-correcting codes are efficient methods for handling \textit{noisy} communication channels in the context of technological networks. However, such elaborate methods differ a lot from the unsophisticated way biological entities are supposed to communicate. Yet, it has been recently shown by
\textit{O. Feinerman} et al. [in: Proceedings of the 33rd ACM symposium on principles of distributed computing, PODC'14. New York, NY: Association for Computing Machinery (ACM). 114--123 (2014; Zbl 1321.68075); Distrib. Comput. 30, No. 5, 339--355 (2017; Zbl 1423.68070)]
that complex coordination tasks such as \textit{rumor spreading} and \textit{majority consensus} can plausibly be achieved in biological systems subject to noisy communication channels, where every message transferred through a channel remains intact with small probability \(\frac{1}{2}+\epsilon \), without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has nevertheless been established only in the case of 2-valued \textit{opinions}: rumor spreading aims at broadcasting a single-bit opinion to all nodes, and majority consensus aims at leading all nodes to adopt the single-bit opinion that was initially present in the system with (relative) majority. In this paper, we extend this previous work to \(k\)-valued opinions, for any constant \(k\ge 2\). Our extension requires to address a series of important issues, some conceptual, others technical. We had to entirely revisit the notion of noise, for handling channels carrying \(k\)-\textit{valued} messages. In fact, we precisely characterize the type of noise patterns for which plurality consensus is solvable. Also, a key result employed in the bivalued case by Feinerman et al. is an estimate of the probability of observing the most frequent opinion from observing the mode of a small sample. We generalize this result to the multivalued case by providing a new analytical proof for the bivalued case that is amenable to be extended, by induction, and that is of independent interest.On Berlekamp-Massey and Berlekamp-Massey-Sakata algorithms.https://www.zbmath.org/1452.682792021-02-12T15:23:00+00:00"Mou, Chenqi"https://www.zbmath.org/authors/?q=ai:mou.chenqi"Fan, Xiaolin"https://www.zbmath.org/authors/?q=ai:fan.xiaolinSummary: The Berlekamp-Massey and Berlekamp-Massey-Sakata algorithms compute a minimal polynomial or polynomial set of a linearly recurring sequence or multi-dimensional array. In this paper some underlying properties of and connections between these two algorithms are clarified theoretically: a unified flow chart for both algorithms is proposed to reveal their connections; the polynomials these two algorithms maintain at each iteration are proved to be reciprocal when both algorithms are applied to the same sequence; and the uniqueness of the choices of polynomials from two critical polynomial sets in the Berlekamp-Massey-Sakata algorithm is investigated.
For the entire collection see [Zbl 1428.68016].On the steady state analysis of covariance matrix self-adaptation evolution strategies on the noisy ellipsoid model.https://www.zbmath.org/1452.903262021-02-12T15:23:00+00:00"Hellwig, Michael"https://www.zbmath.org/authors/?q=ai:hellwig.michael"Beyer, Hans-Georg"https://www.zbmath.org/authors/?q=ai:beyer.hans-georgSummary: This paper addresses the analysis of covariance matrix self-adaptive Evolution Strategies (CMSA-ES) on a subclass of quadratic functions subject to additive Gaussian noise: the noisy ellipsoid model. To this end, it is demonstrated that the dynamical systems approach from the context of isotropic mutations can be transferred to ES that also control the covariance matrix. Theoretical findings such as the component-wise quadratic progress rate or the self-adaptation response function can thus be reused for the CMSA-ES analysis. By deriving the steady state quantities approached on the noisy ellipsoid model for constant population size, a detailed description of the asymptotic CMSA-ES behavior is obtained. By providing self-adaptive ES with a population control mechanism, despite noise disturbances, the algorithm is able to realize continuing progress towards the optimum. Regarding the population control CMSA-ES (pcCMSA-ES), the analytical findings allow to specify its asymptotic long-term behavior and to identify influencing parameters. The finally obtained convergence rate matches the theoretical lower bound of all comparison-based direct search algorithms.Speeding up multi-exponentiation algorithm on a multicore system.https://www.zbmath.org/1452.682662021-02-12T15:23:00+00:00"Fathy, Khaled A."https://www.zbmath.org/authors/?q=ai:fathy.khaled-a"Bahig, Hazem M."https://www.zbmath.org/authors/?q=ai:bahig.hazem-m"Farag, Mohamed S."https://www.zbmath.org/authors/?q=ai:farag.mohamed-sSummary: A public key cryptosystem is a basic tool to protect data security. Most public key cryptosystem schemes include time consuming operations such as the modular multi exponentiation. To address this problem, a new parallel algorithm for the modular multi exponentiation is introduced. The proposed algorithm is based on parallelizing the binary method. The experimental study on a multicore system shows that the running time of the proposed algorithm is smaller than the previous parallel algorithm in the cases of large data sizes under different number of processors. The percentage of improvement is up to 55\% compared with the previous algorithm.Foundations of applied mathematics. Volume 2. Algorithms, approximation, optimization.https://www.zbmath.org/1452.000142021-02-12T15:23:00+00:00"Humpherys, Jeffrey"https://www.zbmath.org/authors/?q=ai:humpherys.jeffrey"Jarvis, Tyler J."https://www.zbmath.org/authors/?q=ai:jarvis.tyler-jPublisher's description: This textbook, geared toward advanced undergraduate and beginning graduate students in mathematics, data science, and machine learning, presents the foundations of algorithms, approximation, and optimization -- essential topics in modern applied and computational mathematics
The authors provide a unified treatment of several topics that do not usually appear together:
\begin {itemize}
\item Theory and analysis of algorithms for mathematicians and data science students;
\item Probability and its applications;
\item Theory and applications of approximation, including Fourier series, wavelets, and polynomial approximation; and
\item Theory and practice of optimization, including dynamic optimization
\end {itemize}
When used in concert with the free supplemental lab materials, this book teaches not only the theory but also the computational practice of modern mathematical methods, inviting students to engage deeply with the mathematical ideas and guiding them to technical proficiency while answering the age-old question ``When am I going to use this?''
For Vol. 1 see [Zbl 1375.00006].Online weight balancing on the unit circle.https://www.zbmath.org/1452.682462021-02-12T15:23:00+00:00"Fujiwara, Hiroshi"https://www.zbmath.org/authors/?q=ai:fujiwara.hiroshi"Seki, Takahiro"https://www.zbmath.org/authors/?q=ai:seki.takahiro"Fujito, Toshihiro"https://www.zbmath.org/authors/?q=ai:fujito.toshihiroSummary: We consider a problem as follows: Given unit weights arriving in an online manner with the total cardinality unknown, upon each arrival we decide where to place it on the unit circle in \(\mathbb {R}^{2}\). The objective is to set the center of mass of the placed weights as close to the origin as possible. We apply competitive analysis defining the competitive difference as a performance measure. We first present an optimal strategy for placing unit weights which achieves a competitive difference of \(\frac{1}{5}\). We next consider a variant in which the destination of each weight must be chosen from a set of positions that equally divide the unit circle. We give a simple strategy whose competitive difference is 0.35. Moreover, in the offline setting, several conditions for the center of mass to lie at the origin are derived.
For the entire collection see [Zbl 1318.68008].Dual parameterization of weighted coloring.https://www.zbmath.org/1452.681292021-02-12T15:23:00+00:00"Araújo, Júlio"https://www.zbmath.org/authors/?q=ai:araujo.julio-cesar-silva"Campos, Victor A."https://www.zbmath.org/authors/?q=ai:campos.victor-a"Lima, Carlos Vinícius G. C."https://www.zbmath.org/authors/?q=ai:lima.carlos-vinicius-g-c"dos Santos, Vinícius Fernandes"https://www.zbmath.org/authors/?q=ai:fernandes-dos-santos.vinicius"Sau, Ignasi"https://www.zbmath.org/authors/?q=ai:sau.ignasi"Silva, Ana"https://www.zbmath.org/authors/?q=ai:silva.ana-carolina|silva.ana-maria-f|silva.ana-l|silva.ana-t-cSummary: Given a graph \(G\), a proper \(k\)-coloring of \(G\) is a partition \(c = (S_i)_{i \in [1, k]}\) of \(V(G)\) into \(k\) stable sets \(S_1, \ldots, S_k\). Given a weight function \(w : V(G) \rightarrow \mathbb{R}^+\), the weight of a color \(S_i\) is defined as \(w(i) = \max_{v \in S_i} w(v)\) and the weight of a coloring \(c\) as \(w(c) = \sum_{i=1}^k w(i)\).
\textit{D. J. Guan} and \textit{X. Zhu} [Inf. Process. Lett. 61, No. 2, 77--81 (1997; Zbl 1336.05041)]
defined the weighted chromatic number of a pair \((G, w)\), denoted by \(\sigma (G, w)\), as the minimum weight of a proper coloring of \(G\). The problem of determining \(\sigma (G, w)\) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on \(n\)-vertex trees in time \(n^{o(\log n)}\) unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph \((G, w)\) and an integer \(k\), is \(\sigma (G, w) \le \sum_{v \in V(G)} w(v) - k\)? This parameterization has been recently considered by
\textit{B. Escoffier} [Lect. Notes Comput. Sci. 9941, 50--61 (2016; Zbl 1417.05064)],
who provided an FPT algorithm running in time \(2^{{\mathcal{O}}(k \log k)} \cdot n^{{\mathcal{O}}(1)} \), and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time \(9^k \cdot n^{\mathcal{O}(1)}\), and prove that no algorithm in time \(2^{o(k)} \cdot n^{\mathcal{O}(1)}\) exists under the ETH. On the other hand, we present a kernel with at most \((2^{k-1} + 1) (k - 1)\) vertices, and rule out the existence of polynomial kernels unless \(\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}\), even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.