Search

The fair k -center problem has been paid lots of attention recently. In the fair k -center problem, we are given a set X of points in a metric space and a parameter k ∈ Z + , where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k -center problem objective is minimized. In this paper, we consider the fair k -center problem with outliers and capacity constraints, denoted as the fair k -center with outliers (F k CO) problem and the capacitated fair k -center (CF k C) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + ϵ) -approximations with FPT time for the F k CO and CF k C problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the F k CO problem with some reasonable assumptions. [ABSTRACT FROM AUTHOR]

A new algorithm is proposed in this paper for computing the nearest polynomial to multiple given polynomials with a given zero in the real case, where the distance between polynomials is defined by the weighted ℓ 2 , q norm (0 < q ≤ 2). First, the problem is formulated as a univariate constrained non-convex minimization problem, where prior information of the coefficients of the polynomial can be embedded by selecting proper weights. Then, an iteratively reweighted algorithm is designed to solve the obtained problem, and also the convergence and rate of convergence are uniformly demonstrated for all q in (0 , 2 ]. Since all the existing methods for computing the nearest polynomial to multiple given polynomials with a given zero are limited to the real case, we ingeniously extend the results to the complex case. Finally, two representative examples that separately compute the nearest real and complex polynomials are presented to show the effectiveness of the proposed algorithm. • A weighted ℓ 2 , q -norm based minimization problem is constructed with prior information of polynomial embedded. • After converting the problem into a univariate problem, an iteratively reweighted algorithm is proposed to solve it. • Using properties of a concave function, convergence and rate of convergence of the proposed algorithm are provided. • It is the first time to study computation of the nearest polynomial to multiple given polynomials with a given zero in the complex case. [ABSTRACT FROM AUTHOR]

Self-stabilization is a general paradigm that characterizes the ability of a distributed system to recover from transient faults. Since its introduction by Dijkstra in 1974, self-stabilization has been successfully applied to efficiently solve many networking tasks. However, most of the literature focuses on bidirectional networks. Now, in today's networks such as WSNs, some communication channels may be one-way only. Considering such network topologies, a.k.a. directed graphs, makes self-stabilization more complicated, and sometimes even impossible. In this paper, we investigate the gap in terms of requirements and efficiency when considering a directed graph instead of an undirected one as network topology for a self-stabilizing algorithm. Our case study is a variant of a synchronous unison algorithm proposed by Arora et al.; the synchronous unison being a clock synchronization problem. • We address self-stabilization of dynamic problems in anonymous directed networks. • We propose a topology-related necessary condition to solve synchronous unison in directed networks. • We present a simple self-stabilizing synchronous unison algorithm for directed networks. • We study conditions under which the proposed algorithm is self-stabilizing, and at what cost. [ABSTRACT FROM AUTHOR]

This paper considers the inverse p -median location problem with variable edge lengths and variable vertex weights on general graphs in which the modification costs are the fuzzy random variables. We present a model for the problem in fuzzy random environment in which the objective value is computed by conditional value at risk criterion. Then, we show that the problem is NP-hard under this criterion. Therefore, a new hybrid modified particle swarm optimization algorithm is proposed to obtain the approximate optimal solution of the proposed model. Finally, computational experiments are given to illustrate high efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Approximating the roots of a holomorphic function in an input box is a fundamental problem in many domains. Most algorithms in the literature for solving this problem are conditional, i.e., they make some simplifying assumptions, such as, all the roots are simple or there are no roots on the boundary of the input box, or the underlying machine model is Real RAM. Root clustering is a generalization of the root approximation problem that allows for errors in the computation and makes no assumption on the multiplicity of the roots. An unconditional algorithm for computing a root clustering of a holomorphic function was given by Yap, Sagraloff and Sharma in 2013 [36]. They proposed a subdivision based algorithm using effective predicates based on Pellet's test while avoiding any comparison with zeros (using soft zero comparisons instead). In this paper, we analyze the running time of their algorithm. We use the continuous amortization framework to derive an upper bound on the size of the subdivision tree. We specialize this bound to the case of polynomials and some simple transcendental functions such as exponential and trigonometric sine. We show that the algorithm takes exponential time even for these simple functions, unlike the case of polynomials. We also derive a bound on the bit-precision used by the algorithm. To the best of our knowledge, this is the first such result for holomorphic functions. We introduce new geometric parameters, such as the relative growth of the function on the input box, for analyzing the algorithm. Thus, our estimates naturally generalize the known results, i.e., for the case of polynomials. [ABSTRACT FROM AUTHOR]

In this paper, we propose a distributed Grover's algorithm, and it requires fewer qubits and has a linear advantage in time complexity compared to the original Grover's algorithm. More exactly, to search for a target in an unstructured database with N elements, Grover's algorithm can get the target with query complexity O (N) , but our distributed Grover's algorithm with K computing nodes can get the target with query complexity O ( N K ) , and the number of qubits inputted in our distributed Grover's algorithm is ⌊ log ⁡ K ⌋ less than that in Grover's algorithm. In addition, we propose an efficient algorithm of constructing quantum circuits for realizing the oracle corresponding to any Boolean function with conjunctive normal form (CNF). • We propose a distributed Grover's algorithm with lower query times and smaller number of input bits. • We propose an efficient algorithm of constructing quantum circuits for realizing the oracle corresponding to any Boolean function with CNF. [ABSTRACT FROM AUTHOR]

Edge computing is an emerging promising computing paradigm, which can significantly reduce the service latency by moving computing and storage demands to the edge of the network. Resource-constrained edge servers may fail to process multiple tasks simultaneously when several time-delay-sensitive and computationally demanding tasks are offloaded to only one edge server, and results in some issues such as high task processing costs. In this paper, we introduce a novel idea by dividing one task into several sub-tasks via the dependencies within the task and then offloading the sub-tasks to other edge servers in light of high concurrency for synchronization to minimize the total cost of task processing. To address the challenge of task dependencies and adaptation to dynamic scenes, we propose a Multi-Task Dependency Offloading Algorithm (MTDOA) based on deep reinforcement learning. The task offloading decision is modeled as a Markov decision process, and then a graph attention network is applied to extract the dependency information of different tasks, while LSTM and DQN are combined to deal with sequential problems. The simulation results show that the proposed MTDOA has better convergence ability compared with the baseline algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we consider the edge searching problem and the fast searching problem with constraints on some vertices. The edge searching problem was introduced by Megiddo et al. (1988) [15] , in which a group of searchers want to capture an invisible robber. The fast searching problem was introduced by Dyer et al. (2008) [8]. One constraint we consider for these two searching models is that a subset of vertices, called start vertices, are initially occupied by searchers. We want to find the minimum number of additional searchers to capture the robber. Another constraint is that there are some vertices, called halt vertices, which have to be occupied by searchers at the end of the searching process. For the edge searching on a tree containing only start vertices, we propose an O (n log ⁡ n) -time algorithm for computing the edge search number, where n is the number of vertices. For the edge searching on a tree with start vertices and halt vertices, we give an O (n 2) -time algorithm to compute the edge search number. For the fast searching on a tree that contains only start vertices, we present a linear-time algorithm for computing the fast search number. For the fast searching on a tree with n vertices that contains s start vertices and h halt vertices, we propose an O ((s + h) n) -time algorithm to compute the fast search number. For the edge searching (respectively, fast searching) with only halt vertices, we reduce the problem to the edge searching (respectively, fast searching) with start vertices. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a problem called Minimum subTree problem with Degree Weights , or MTDW. This problem generalized covering tree problems like Spanning Tree , Steiner Tree , Minimum Branch Vertices , Minimum Leaf Spanning Tree , or Prize Collecting Steiner Tree. It consists, given an undirected graph G = (V , E) , a set of m + 1 mappings C 1 , C 2 , ... , C m , D : V × N → Z , a set of m integers K 1 , K 2 , ... , K m ∈ Z and a positive integer ℓ , in the search of a forest (T 1 , T 2 , ... , T ℓ) containing ℓ node-disjoint trees of G. Along with K j , the mapping C j defines a constraint that should be satisfied by the trees of the forest. For each tree T i , it associates each node v of V to the score C j (v , d T i (v)) where d T i (v) is the degree of v in T i (possibly 0 if the node is not in T i). The sum ∑ v ∈ V C j (v , d T i (v)) should not exceed K j. In addition, the forest should minimize ∑ i = 1 ℓ ∑ v ∈ V D (v , d T i (v)). We proceed to a parameterized analysis of the MTDW problem with regard to four parameters that are the number of constraints m , the value ℓ , the treewidth of the input graph G and Δ, the minimum degree above which all the constraints and D are constant (for every j ∈ 〚 1 , m 〛 , v ∈ V and d ≥ Δ , C j (v , d) = C j (v , Δ) , and D (v , d) = D (v , Δ)). For this problem, we provide a first dichotomy P versus NP -hard depending whether the previous parameters are fixed to be constant or not and a second dichotomy FPT versus W[1] -hard depending whether each of these parameters is constant, considered as a parameter, or disregard. As a side effect, we obtained parameterized algorithms, previously undescribed, for problems such that Budget Steiner Tree problem with Profits , Minimum Branch Vertices , Generalized branch vertices , or k -Bottleneck Steiner Tree. [ABSTRACT FROM AUTHOR]

ECDSA is a standardized signature scheme and is widely used in many fields. However, most two-party ECDSA require a complicated multi-party computation technique to compute the multiplication of many shared secrets and necessitate expensive zero-knowledge proofs to deal with malicious adversaries. In this paper, we propose a simple yet fast two-party signing protocol based on ECDSA security, whose signing operation of each party is similar to the original ECDSA signing algorithm. Our protocol can enjoy the same efficiency as ECDSA and upgrades the existing ECDSA application to two-party scenario friendly. For this purpose, we first introduce a variant of ECDSA called combinatorial ECDSA, which is as secure as the standard ECDSA and can be easily divided into two parts. Then, we devise a two-party signing protocol without complicated multi-party computation from the combinatorial ECDSA and give the security proof based on ECDSA. Compared with the state-of-the-art two-party ECDSA, the signing result of each party in our protocol maintains the structure of ECDSA signature, which can be verified easily and avoids expensive zero-knowledge proofs. Last, we conduct an experimental evaluation, demonstrating that the performance of our combinatorial ECDSA and two-party signature is similar to ECDSA and the experimental results show that our proposed schemes are practical. [ABSTRACT FROM AUTHOR]

The Restricted Subset Feedback Vertex Set problem (R-SFVS) takes a graph G = (V , E) , a terminal set T ⊆ V , and an integer k as the input. The task is to determine whether there exists a subset S ⊆ V ∖ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP -complete even when the input graph is restricted to split graphs. In this paper, we mainly show that R-SFVS in chordal and split graphs can be solved in O (1.1550 | V |) time and exponential space or in O (1.1605 | V |) time and polynomial space, significantly improving all previous results. As a by-product, we show that the Maximum Independent Set problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to Vertex Cover , we obtain an O ⁎ (1.2738 k) -time parameterized algorithm and a tight O (k 2) -kernel for R-SFVS in chordal and split graphs. [ABSTRACT FROM AUTHOR]

In the 2-Club Cluster Vertex Deletion (resp., 2-Club Cluster Edge Deletion) problem the input is a graph G and an integer k , and the goal is to decide whether there is a set of at most k vertices (resp., edges) whose removal from G results in a graph in which the diameter of every connected component is at most 2. In this paper we give algorithms for 2-Club Cluster Vertex Deletion and 2-Club Cluster Edge Deletion whose running times are O ⁎ (3.104 k) and O ⁎ (2.562 k) , respectively. Our algorithms were obtained using automated generation of branching rules. Our results improve the previous O ⁎ (3.303 k) -time algorithm for 2-Club Cluster Vertex Deletion [Liu et al., FAW-AAIM 2012] and the O ⁎ (2.695 k) -time algorithm for 2-Club Cluster Edge Deletion [Abu-Khzam et al., TCS 2023]. [ABSTRACT FROM AUTHOR]

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 − o (1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints. [ABSTRACT FROM AUTHOR]

The Minimum Vertex Cover P roblem is the optimization problem of finding a vertex cover V c of minimal cardinality in a given graph. It is a classic NP-hard problem, and various algorithms have been suggested for it. In this paper, we start with a basic algorithm for solving the problem. Using a probabilistic idea, we use it to develop an improved algorithm. The algorithm is greedy; at each step it adds to the cover a vertex such that the expected cover size, if we continue randomly after this step, is minimal. We study the new algorithm theoretically and empirically, and run simulations to compare its performance to that of some algorithms of a similar nature. [ABSTRACT FROM AUTHOR]

We revisit the maximum satisfiability problem (Max-SAT) in the data stream model. In this problem, the stream consists of m clauses that are disjunctions of literals drawn from n Boolean variables. The objective is to find an assignment to the variables that maximizes the number of satisfied clauses. Chou et al. (FOCS 2020) showed that Ω (n) space is necessary to yield a 2 / 2 + ε approximation of the optimum value; they also presented an algorithm that yields a 2 / 2 − ε approximation of the optimum value using O (ε − 2 log ⁡ n) space. In this paper, we not only focus on approximating the optimum value, but also on obtaining the corresponding Boolean assignment using sublinear o (m n) space. We present randomized single-pass algorithms that w.h.p.1 yield: • A 1 − ε approximation using O ˜ (n / ε 3) space and exponential post-processing time • A 3 / 4 − ε approximation using O ˜ (n / ε) space and polynomial post-processing time. Our ideas also extend to dynamic streams. However, we show that the streaming k -SAT problem, which asks whether one can satisfy all size- k input clauses, must use Ω (n k) space. We also consider the related minimum satisfiability problem (Min-SAT), introduced by Kohli et al. (SIAM J. Discrete Math. 1994), that asks to find an assignment that minimizes the number of satisfied clauses. For this problem, we give a O ˜ (n 2 / ε 2) space algorithm, which is sublinear when m = ω (n) , that yields an α + ε approximation where α is the approximation guarantee of the offline algorithm. If each variable appears in at most f clauses, we show that a 2 f n approximation using O ˜ (n) space is possible. Finally, for the Max-AND-SAT problem where clauses are conjunctions of literals, we show that any single-pass algorithm that approximates the optimal value up to a factor better than 1/2 with success probability at least 2/3 must use Ω (m n) space. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) without an isolated edge, a set D ⊆ E is an edge total dominating set of G if every edge e ∈ E is adjacent to at least one edge of D. The Minimum Edge Total Dominating Set problem is to compute a minimum cardinality edge total dominating set of G. It is known that the decision version of the problem is NP-complete for bipartite graphs, chordal graphs, and planar graphs. On the positive side, the problem is efficiently solvable for trees. In this paper, we further study the complexity of this problem in other graph classes. We design a linear-time algorithm to compute a minimum cardinality edge total dominating set in chain graphs, a subclass of bipartite graphs. We also propose linear-time algorithms for two subclasses of chordal graphs, namely, split graphs and proper interval graphs with no cut vertices. In addition, we show that the problem is APX-complete for graphs with maximum degree 3 and propose an approximation algorithm for the problem in k -regular graphs, where k ≥ 4. We discuss the complexity difference between the Minimum Edge Dominating Set problem and Minimum Edge Total Dominating Set problem which seem to be closely related. [ABSTRACT FROM AUTHOR]

To solve reachability is to determine whether there is a path from one vertex to the other in a graph. Standard graph traversal algorithms such as DFS and BFS take linear time to solve reachability; however, their space complexity is also linear. On the other hand, Savitch's algorithm takes quasipolynomial time, although the space-bound is O (log 2 ⁡ n). In this paper, we study space-efficient algorithms for deciding reachability that runs in polynomial time. We show a polynomial-time algorithm that solves reachability in directed graphs using O (w log ⁡ n) space. Our algorithm requires access to a tree decomposition of width w for the underlying undirected graph of the input. This requirement can be waived for graphs for which recursive balanced vertex separators can be computed space-efficiently. [ABSTRACT FROM AUTHOR]

In this work, we investigate the problem of maximizing nonmonotone DR-submodular function (possibly negative) subject to cardinality constraints on an integer lattice space. We propose a M -Threshold Decrease Algorithm that uses a compensation constant M from a special decomposition h (x) = f (x) − g (x) , which achieves a 1 − e − δ − ϵ approximation guarantee. To ensure that the algorithm ends in finite time, the supremum of δ is δ (ϵ) = ϵ max s ∈ Ω ⁡ h (χ s | 0) 2 k max s ∈ Ω ⁡ g (χ s | 0) + ϵ max s ∈ Ω ⁡ h (χ s | 0). If max s ∈ Ω ⁡ h (χ s | 0) > 2 k max s ∈ Ω ⁡ g (χ s | 0) , there exists ϵ ⁎ = arg ⁡ max ϵ ∈ (0 , 1) ⁡ 1 − e − δ (ϵ) − ϵ such that 1 − e − δ (ϵ ⁎) − ϵ ⁎ > 0. This implies that there is a valid δ such that 1 − e − δ − ϵ > 0. To accelerate the algorithm, we employ a random subset to replace the ground set and propose a Random M -Threshold Decrease Algorithm, where δ (ϵ) = ϵ r max s ∈ Ω ⁡ h (χ s | 0) 2 n k max s ∈ Ω ⁡ g (χ s | 0) + [ k (n − r) + ϵ r ] max s ∈ Ω ⁡ h (χ s | 0) with r being the size of the random subset and n being the size of the ground set. Furthermore, we demonstrate that, based on the DR-ratio γ d and the DS decomposition, the M -Threshold Decrease Algorithm is also suitable for solving the monotone non-DR-submodular maximization problem, achieving a 1 − e − γ d δ − O (ϵ) approximation guarantee. Because γ d is a challenging metric to calculate, we refine the M -Threshold Decrease Algorithm, which can return an estimate of γ d. To the best of our knowledge, this is the first time that a single factor approximation ratio has been proposed for the nonmonotone DR-submodular maximization problem (possibly negative) subject to cardinality constraints. • This paper adopts the decomposition structure to compensate the non-monotonicity and non-negativity for DR-submodular maximization. • Using a compensation constant M , we design a 1 − e − δ − ϵ approximation algorithm, namely M -Threshold Decrease Algorithm. • Based on the DR-ratio γ d , our algorithm is a 1 − e − δ γ d − O (ϵ) approximation algorithm for monotone non-DR-submodular maximization. [ABSTRACT FROM AUTHOR]