Search

We study the computational complexity of (deterministic or randomized) algorithms based on point samples for approximating or integrating functions that can be well approximated by neural networks. Such algorithms (most prominently stochastic gradient descent and its variants) are used extensively in the field of deep learning. One of the most important problems in this field concerns the question of whether it is possible to realize theoretically provable neural network approximation rates by such algorithms. We answer this question in the negative by proving hardness results for the problems of approximation and integration on a novel class of neural network approximation spaces. In particular, our results confirm a conjectured and empirically observed theory-to-practice gap in deep learning. We complement our hardness results by showing that error bounds of a comparable order of convergence are (at least theoretically) achievable. [ABSTRACT FROM AUTHOR]

Reoptimization is a setting in which we are given a good approximate solution of an optimization problem instance and a local modification that slightly changes the instance. The main goal is that of finding a good approximate solution of the modified instance. We investigate one of the most studied scenarios in reoptimization known as Steiner tree reoptimization. Steiner tree reoptimization is a collection of strongly NP -hard optimization problems that are defined on top of the classical Steiner tree problem and for which several constant-factor approximation algorithms have been designed in the last decades. In this paper we improve upon all these results by developing a novel technique that allows us to design polynomial-time approximation schemes. Remarkably, prior to this paper, no approximation algorithm better than recomputing a solution from scratch was known for the elusive scenario in which the cost of a single edge decreases. Our results are best possible since none of the problems addressed in this paper admits a fully polynomial-time approximation scheme, unless P = NP [ABSTRACT FROM AUTHOR]

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seems to escape from the literature. A path containing at least k vertices is considered long. When k ≤ 3 , the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4 , the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4 , the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O (1)) -approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4 . Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies. [ABSTRACT FROM AUTHOR]

Minimizing the weighted completion time of jobs in the unrelated parallel machines model is a fundamental scheduling problem. The first (3 / 2 - c) –approximation algorithm for this problem, for some constant c > 0 , was obtained in the work of Bansal et al. (SIAM J Comput, 2021). A key ingredient in this work was the first dependent-rounding algorithm with a certain guaranteed amount of negative correlation. We improve upon this guaranteed amount from 1/108 to 1/27, thus also improving upon the constant c in the algorithms of Bansal et al. and Li (SIAM J Comput, 2020) for weighted completion time. Given the now-ubiquitous role played by dependent rounding in scheduling and combinatorial optimization, our improved dependent rounding is also of independent interest. [ABSTRACT FROM AUTHOR]

Variational Quantum Algorithms (VQAs) have made great success in the Noisy Intermediate-Scale Quantum (NISQ) era due to their relative resilience to noise and high flexibility relative to quantum resources. Quantum Architecture Search (QAS) aims to enhance the performance of VQAs by refining the structure of the adopted Parameterized Quantum Circuit (PQC). QAS is garnering increased attention owing to its automation, reduced reliance on expert experience, and its ability to achieve better performance while requiring fewer quantum gates than manually designed circuits. However, existing QAS algorithms optimize the structure from scratch for each VQA without using any prior experience, rendering the process inefficient and time-consuming. Moreover, determining the number of quantum gates, a crucial hyper-parameter in these algorithms is a challenging and time-consuming task. To mitigate these challenges, we accelerate the QAS algorithm via a meta-trained generator. The proposed algorithm directly generates high-performance circuits for a new VQA by utilizing a meta-trained Variational AutoEncoder (VAE). The number of quantum gates required in the designed circuit is automatically determined based on meta-knowledge learned from a variety of training tasks. Furthermore, we have developed a meta-predictor to filter out circuits with suboptimal performance, thereby accelerating the algorithm. Simulation results on variational quantum compiling and Quantum Approximation Optimization Algorithm (QAOA) demonstrate the superior performance of our method over a state-of-the-art algorithm, namely Differentiable Quantum Architecture Search (DQAS). [ABSTRACT FROM AUTHOR]

In this work, we introduce a multi-vehicle (or multi-postman) extension of the classical Mixed Rural Postman Problem, which we call the Min–Max Mixed Rural Postmen Cover Problem (MRPCP). The MRPCP is defined on a mixed graph G = (V , E , A) , where V is the vertex set, E denotes the (undirected) edge set and A represents the (directed) arc set. Let F ⊆ E ( H ⊆ A ) be the set of required edges (required arcs). There is a nonnegative weight associated with each edge and arc. The objective is to determine no more than k closed walks to cover all the required edges in F and all the required arcs in H such that the weight of the maximum weight closed walk is minimized. By replacing closed walks with (open) walks in the MRPCP, we obtain the Min–Max Mixed Rural Postmen Walk Cover Problem (MRPWCP). The Min–Max Mixed Chinese Postmen Cover Problem (MCPCP) is a special case of the MRPCP where F = E and H = A . The Min–Max Stacker Crane Cover Problem (SCCP) is another special case of the MRPCP where F = ∅ and H = A For the MRPCP with the input graph satisfying the weakly symmetric condition, i.e., for each arc there exists a parallel edge whose weight is not greater than this arc, we devise a 27 4 -approximation algorithm. This algorithm achieves an approximation ratio of 33 5 for the SCCP with the weakly symmetric condition. Moreover, we obtain the first 5-approximation algorithm (4-approximation algorithm) for the MRPWCP (MCPCP) with the weakly symmetric condition. [ABSTRACT FROM AUTHOR]

Quantum approximate optimization algorithms are hybrid quantum-classical variational algorithms designed to approximately solve combinatorial optimization problems such as the MAX-CUT problem. In spite of its potential for near-term quantum applications, it has been known that quantum approximate optimization algorithms have limitations for certain instances to solve the MAX-CUT problem, at any constant level p. Recently, the recursive quantum approximate optimization algorithm, which is a non-local version of quantum approximate optimization algorithm, has been proposed to overcome these limitations. However, it has been shown by mostly numerical evidences that the recursive quantum approximate optimization algorithm outperforms the original quantum approximate optimization algorithm for specific instances. In this paper, we analytically prove that the recursive quantum approximate optimization algorithm is more competitive than the original one to solve the MAX-CUT problem for complete graphs with respect to the approximation ratio. [ABSTRACT FROM AUTHOR]

This paper constructs an interval partition linearization algorithm for solving minimax linear fractional programming (MLFP) problem. In this algorithm, MLFP is converted and decomposed into a series of linear programs by dividing the outer 1-dimensional space of the equivalent problem (EP) into polynomially countable intervals. To improve the computational efficiency of the algorithm, two new acceleration techniques are introduced, in which the regions in outer space where the optimal solution of EP does not exist are largely deleted. In addition, the global convergence of the proposed algorithm is summarized, and its computational complexity is illustrated to reveal that it is a fully polynomial time approximation scheme. Finally, the numerical results demonstrate that the proposed algorithm is feasible and effective. [ABSTRACT FROM AUTHOR]

In the general max–min fair allocation problem, there are m players and n indivisible resources, each player has his/her own utilities for the resources, and the goal is to find an assignment that maximizes the minimum total utility of resources assigned to a player. The problem finds many natural applications such as bandwidth distribution in telecom networks, processor allocation in computational grids, and even public-sector decision making. We introduce an over-estimation strategy to design approximation algorithms for this problem. When all utilities are positive, we obtain an approximation ratio of c 1 - ϵ , where c is the maximum ratio of the largest utility to the smallest utility of any resource. When some utilities are zero, we obtain an approximation ratio of (1 + 3 c ^ + O (δ c ^ 2)) , where c ^ is the maximum ratio of the largest utility to the smallest positive utility of any resource. [ABSTRACT FROM AUTHOR]

We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial time. This result was conjectured by Wegener (Automata, Languages and Programming, ICALP, Berlin, 2005). More precisely, denoting by n , m , w max , and w min the number of vertices and edges as well as the maximum and minimum edge weight of the MST instance, we prove that simulated annealing with initial temperature T 0 ≥ w max and multiplicative cooling schedule with factor 1 - 1 / ℓ , where ℓ = ω (m n ln (m)) , with probability at least 1 - 1 / m computes in time O (ℓ (ln ln (ℓ) + ln (T 0 / w min))) a spanning tree with weight at most 1 + κ times the optimum weight, where 1 + κ = (1 + o (1)) ln (ℓ m) ln (ℓ) - ln (m n ln (m)) . Consequently, for any ϵ > 0 , we can choose ℓ in such a way that a (1 + ϵ) -approximation is found in time O ((m n ln (n)) 1 + 1 / ϵ + o (1) (ln ln n + ln (T 0 / w min))) with probability at least 1 - 1 / m . In the special case of so-called (1 + ϵ) -separated weights, this algorithm computes an optimal solution (again in time O ((m n ln (n)) 1 + 1 / ϵ + o (1) (ln ln n + ln (T 0 / w min))) ), which is a significant speed-up over Wegener's runtime guarantee of O (m 8 + 8 / ϵ) . Our tighter upper bound also admits the result that in some situations a hybridization of simulated annealing and the (1 + 1) EA can lead to stronger runtime guarantees than either algorithm alone. [ABSTRACT FROM AUTHOR]

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles. [ABSTRACT FROM AUTHOR]

We study the Non-preemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Non-preemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a (5 / 3 + ε) -approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption (1 + ε) OPT . The remaining jobs fit into a thin container of height 1. This AEPTAS is used as a subroutine to acquire the (5 / 3 + ε) -approximation algorithm. The previous best result for NPDM was a 2.7-approximation based on FFDH (Ranjan et al., in: 2015 IEEE symposium on computers and communication (ISCC), pp 758–763, IEEE, 2015). One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg's algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above, such that it does not exceed the bound of (5 / 3 + ε) OPT . [ABSTRACT FROM AUTHOR]

We study several two-machine shop scheduling problems, namely flow shop, job shop and open shop scheduling problems under linear constraints. In these problems, the processing times of two stages of jobs are also decision variables and satisfy a system of linear constraints. The goal of each problem is to determine the processing time of each job, and to schedule the jobs to the shop machine such that the makespan, i.e., the completion time of all jobs, is minimized. These problems can find application in various areas, such as industrial production, advertising and automotive maintenance. We study the computational complexity and propose polynomial-time optimal or approximation algorithms for them. In particular, we show that although a two-machine flow shop scheduling problem and a two-machine job shop scheduling problem without recirculation can be solved in polynomial time, the problems where processing times satisfy linear constraints are generally NP-hard in the strong sense. Then, we design algorithms for various settings of these problems. We design polynomial-time algorithms for them when there are a fixed number of constraints. For the general case, we first propose a simple 2-approximation algorithm, and then design a polynomial-time approximation schemes. In contrast to the previous two problems, we show that the two-machine open shop scheduling problem under linear constraints can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics. Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric. However, exact geodesic computation is time-consuming and has high memory usage, limiting wider application of geodesic Voronoi diagrams (GVDs). In order to overcome this issue, instead of using exact methods, we reformulate a graph method based on Steiner point insertion, as an effective way to obtain geodesic distances. Further, since a bisector comprises hyperbolic and line segments, we utilize Apollonius diagrams to encode complicated structures, enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples. Based on these strategies, we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces. We also suggest a measure for evaluating similarity of our results to the exact GVD. Although our GVD results are constructed using approximate geodesic distances, we can get GVD results similar to exact results by inserting Steiner points on triangle edges. Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods. [ABSTRACT FROM AUTHOR]

A method for measuring the spectrum of admittance spectrum of piezoelectric elements in the pulsed excitation mode and its digital implementation are proposed. The method reduces the duration of measurements, and the processing algorithm increases the accuracy of the estimated parameters. To determine the characteristic frequencies, Q-factor, and parallel capacitance, an algorithm of fractional-rational approximation of the admittance spectrum in the resonant frequency range is used. [ABSTRACT FROM AUTHOR]

Many network design problems deal with the design of low-cost networks that are resilient to the failure of their elements (such as nodes or links). One such problem is Connectivity Augmentation, with the goal of cheaply increasing the (edge- or node-)connectivity of a given network from a value k to k + 1 . The problem is NP-hard for k ≥ 1 , and the most studied setting focuses on the case of edge-connectivity with k = 1 . In this work, we give a 1.892-approximation algorithm for the NP-hard problem of augmenting the node-connectivity of any given graph from 1 to 2, which improves upon the state-of-the-art approximation previously developed in the literature. The starting point of our work is a known reduction from Connectivity Augmentation to some specific instances of the Node-Steiner Tree problem, and our result is obtained by developing a new and simple analysis of the iterative randomized rounding technique when applied to such Steiner Tree instances. Our results also imply a 1.892-approximation algorithm for the problem of augmenting the edge-connectivity of a given graph from any value k to k + 1 . While this does not beat the best approximation factor known for this problem, a key point of our work is that the analysis of our approximation factor is less involved when compared to previous results in the literature. In addition, our work gives new insights on the iterative randomized rounding method, that might be of independent interest. [ABSTRACT FROM AUTHOR]

We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the rooted Subtree Prune-and-Regraft (rSPR) distance between two phylogenetic trees. Our algorithm is combinatorial and its running time is quadratic in the input size. To prove the approximation guarantee, we construct a feasible dual solution for a novel exponential-size linear programming formulation. In addition, we show this linear program has a smaller integrality gap than previously known formulations, and we give an equivalent compact formulation, showing that it can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of n items, each associated with a non-negative weight, and T time periods with non-decreasing capacities W 1 ≤ ⋯ ≤ W T . When item i is inserted at time t, we gain a profit of p it ; however, this item remains in the knapsack for all subsequent periods. The goal is to decide if and when to insert each item, subject to the time-dependent capacity constraints, with the objective of maximizing our total profit. Interestingly, this setting subsumes as special cases a number of recently-studied incremental knapsack problems, all known to be strongly NP-hard. Our first contribution comes in the form of a polynomial-time (1 2 - ϵ) -approximation for the generalized incremental knapsack problem. This result is based on a reformulation as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys–Tardos algorithm for the generalized assignment problem. Combined with further enumeration-based self-reinforcing ideas and new structural properties of nearly-optimal solutions, we turn our algorithm into a quasi-polynomial time approximation scheme (QPTAS). Hence, under widely believed complexity assumptions, this finding rules out the possibility that generalized incremental knapsack is APX-hard. [ABSTRACT FROM AUTHOR]

The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e. There is a polynomial time 4-approximation for the problem (Bar-Noy et al. STOC 2001) and also a QPTAS (Höhn et al. ICALP 2018). In this paper we study fixed-parameter algorithms for the problem. We show that it is W[1]-hard but it becomes FPT if we can slighly violate the edge demands (resource augmentation) and also if there are at most k different task sizes. Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of f (k) ⋅ n O 휖 (1) that outputs a solution with at most (1 + 휖)k tasks or asserts that there is no solution with at most k tasks. In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times. We show that the other two algorithms extend also to the weighted case of the problem, at the expense of losing a factor of 1 + 휖 in the cost of the selected tasks. [ABSTRACT FROM AUTHOR]

While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of 2 for the unweighted matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is based on the versatile local ratio technique and also applies to generalizations such as weighted hypergraph matchings. However, the framework for the analysis fails for the related problem of weighted matroid intersection and as a result the approximation guarantee for weighted instances did not match the factor 2 achieved by the greedy algorithm for unweighted instances.Our main result closes this gap by developing a semi-streaming algorithm with an approximation guarantee of 2 + ε for weighted matroid intersection, improving upon the previous best guarantee of 4 + ε . Our techniques also allow us to generalize recent results by Levin and Wajc on submodular maximization subject to matching constraints to that of matroid-intersection constraints. While our algorithm is an adaptation of the local ratio technique used in previous works, the analysis deviates significantly and relies on structural properties of matroid intersection, called kernels. Finally, we also conjecture that our algorithm gives a (k + ε) approximation for the intersection of k matroids but prove that new tools are needed in the analysis as the structural properties we use fail for k ≥ 3 . [ABSTRACT FROM AUTHOR]

We consider the graph k-partitioning problem under the min-max objective, termed as Minmax k -cut. The input here is a graph G = (V , E) with non-negative integral edge weights w : E → Z + and an integer k ≥ 2 and the goal is to partition the vertices into k non-empty parts V 1 , ... , V k so as to minimize max i = 1 k w (δ (V i)) . Although minimizing the sum objective ∑ i = 1 k w (δ (V i)) , termed as Minsum k -cut, has been studied extensively in the literature, very little is known about minimizing the max objective. We initiate the study of Minmax k -cut by showing that it is NP-hard and W[1]-hard when parameterized by k, and design a parameterized approximation scheme when parameterized by k. The main ingredient of our parameterized approximation scheme is an exact algorithm for Minmax k -cut that runs in time (λ k) O (k 2) n O (1) + O (m) , where λ is value of the optimum, n is the number of vertices, and m is the number of edges. Our algorithmic technique builds on the technique of Lokshtanov, Saurabh, and Surianarayanan (FOCS, 2020) who showed a similar result for Minsum k -cut. Our algorithmic techniques are more general and can be used to obtain parameterized approximation schemes for minimizing ℓ p -norm measures of k-partitioning for every p ≥ 1 . [ABSTRACT FROM AUTHOR]

We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of twins, with a novel construction of a "good" cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem. [ABSTRACT FROM AUTHOR]

We investigate offline and online algorithms for Round - UFPP , the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. Round - UFPP is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for Round - UFPP without the NBA. We first study offline Round - UFPP for a restricted class of instances, called α -small, where the size of each flow is at most α times the capacity of its bottleneck edge, and present an O (log (1 / (1 - α))) -approximation algorithm. Next, our main result is an online O (log log c max) -competitive algorithm for Round - UFPP where c max is the largest edge capacity, improving upon the previous best bound of O (log c max) due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline O (min (log n , log m , log log c max)) -approximation algorithm and an online O (min (log m , log log c max)) -competitive algorithm for Round - UFPP , where n is the number of flows and m is the number of edges. [ABSTRACT FROM AUTHOR]

In this paper, we devise improved approximation algorithms for the Min–Max Rural Postmen Cover Problem (RuralPostCover) and the Min–Max Chinese Postmen Cover Problem (ChinesePostCover), which are natural extensions of the classical Rural Postman Problem and the Chinese Postman Problem where multiple postmen are available. These results are based on some key observations, a new approach to derive closed walks from (open) walks and an efficient postmen allocation procedure in the literature. As an application of the algorithm for RuralPostCover, we give the first constant-factor approximation algorithms for the Min–Max Subtree Cover Problem (SubtreeCover) and its generalization, called the Min–Max Steiner Tree Cover Problem with Vertex Weights (SteinerTreeCover), using simple approximation preserving reductions. Moreover, we devise specialized algorithms for SteinerTreeCover (SubtreeCover) with better approximation ratios. [ABSTRACT FROM AUTHOR]

We give better approximation ratios for two Steiner Tree variants by combining known algorithms: the optimum 3 -decomposition and iterative randomized rounding. The first problem is Steiner Tree with minimum number of Steiner points and bounded edge length problem ( S M T - M S P ). The input consists of a set of terminals R in the Euclidean space R 2 . A feasible solution is a Steiner tree τ spanning R with Steiner points S such that every edge in τ has length at most 1 . The objective is to minimize S . Previously, the best approximation ratio for S M T - M S P was 1 + ln (4) + ϵ ≈ 2.386 . We present a polynomial time algorithm with ratio 2.277 . The second problem is Steiner Tree in quasi-bipartite graphs. It is a Steiner Tree problem on graph G = (V , E , c) with terminal set R when the edge set E does not include any edge between two vertices in V \ R . The best-known approximation ratio for this problem is 73 60 , We improve this ratio to 298 245 . [ABSTRACT FROM AUTHOR]

Collective graphical model (CGM) is a probabilistic model that provides a framework for analyzing aggregated count data. Maximum a posteriori (MAP) inference of unobserved variables under given observations is one of the essential operations in CGM. Because the MAP inference problem is known to be NP-hard in general, the current mainstream approach is to solve an alternative problem obtained by approximating the objective function and applying continuous relaxation. However, this approach has two significant drawbacks. First, the quality of the solution deteriorates when the values in the count data are negligible due to the inaccuracy of Stirling's approximation. Second, the application of continuous relaxation causes the violation of integrality constraints. This paper proposes novel algorithms for MAP inference in CGMs on path graphs to overcome these problems. Our method is based on the discrete difference of convex algorithm (DCA); DCA is a general framework to minimize the sum of a convex function and a concave function by repeatedly minimizing surrogate functions. Utilizing the particular structure of path graphs, we efficiently solve the surrogate function minimization by minimum convex cost flow algorithms. Furthermore, our approach also leads to a new method of solving another important task; MAP inference of the sample size in CGM on path graphs. Our method is naturally applicable to this task, allowing us to design very efficient algorithms. Experimental results on synthetic and real-world datasets show the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Tverberg's theorem states that for any k ≥ 2 and any set P ⊂ R d of at least (d + 1) (k - 1) + 1 points in d dimensions, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem of finding the partition lies in the complexity class CLS = PPAD ∩ PLS , but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa (SODA 2019) gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set P ⊂ R d and any k ∈ { 2 , ⋯ , n } in O (n d ⌈ log k ⌉) time a k-partition of P such that there is a ball of radius O ((k / n) diam (P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria's method (Israel Journal Math., 1992) to reduce the Tverberg problem to the colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem. [ABSTRACT FROM AUTHOR]

Multiobjective optimization approaches have allowed the improvement of technical features in industrial processes, focusing on more accurate approaches for solving complex engineering problems and support decision-making. This paper proposes a hybrid approach to optimize the 3D printing technology parameters, integrating the design of experiments and multiobjective optimization methods, as an alternative to classical parametrization design used in machining processes. Alongside the approach, a multiobjective differential evolution with uniform spherical pruning (usp-MODE) algorithm is proposed to serve as an optimization tool. The parametrization design problem considered in this research has the following three objectives: to minimize both surface roughness and dimensional accuracy while maximizing the mechanical resistance of the prototype. A benchmark with non-dominated sorting genetic algorithm II (NSGA-II) and with the classical sp-MODE is used to evaluate the performance of the proposed algorithm. With the increasing complexity of engineering problems and advances in 3D printing technology, this study demonstrates the applicability of the proposed hybrid approach, finding optimal combinations for the machining process among conflicting objectives regardless of the number of decision variables and goals involved. To measure the performance and to compare the results of metaheuristics used in this study, three Pareto comparison metrics have been utilized to evaluate both the convergence and diversity of the obtained Pareto approximations for each algorithm: hyper-volume (H), g-Indicator (G), and inverted generational distance. To all of them, ups-MODE outperformed, with significant figures, the results reached by NSGA-II and sp-MODE algorithms. [ABSTRACT FROM AUTHOR]

We study algorithms for the sliding-window model, an important variant of the data-stream model, in which the goal is to compute some function of a fixed-length suffix of the stream. We extend the smooth-histogram framework of Braverman and Ostrovsky (FOCS 2007) to almost-smooth functions, which includes all subadditive functions. Specifically, we show that if a subadditive function can be 1 + ε -approximated in the insertion-only streaming model, then it can be 2 + ε -approximated also in the sliding-window model with space complexity larger by factor O ε - 1 log w , where w is the window size. We demonstrate how our framework yields new approximation algorithms with relatively little effort for a variety of problems that do not admit the smooth-histogram technique. For example, in the frequency-vector model, a symmetric norm is subadditive and thus we obtain a sliding-window 2 + ε -approximation algorithm for it. Another example is for streaming matrices, where we derive a new sliding-window 2 + ε -approximation algorithm for Schatten 4-norm. We then consider graph streams and show that many graph problems are subadditive, including maximum submodular matching, minimum vertex-cover, and maximum k-cover, thereby deriving sliding-window O 1 -approximation algorithms for them almost for free (using known insertion-only algorithms). Finally, we design for every d ∈ 1 , 2 an artificial function, based on the maximum-matching size, whose almost-smoothness parameter is exactly d. [ABSTRACT FROM AUTHOR]

Consider the following Stochastic Score Classification problem. A doctor is assessing a patient's risk of developing a disease and can perform n different binary tests on the patient. The probability that test i is positive is p i and the outcomes of the n tests are independent. A patient's score is the total number of positive tests. Possible scores thus range between 0 and n. This range is divided into subranges, corresponding to risk classes (e.g., LOW, MEDIUM, or HIGH risk). Each test has an associated cost. To reduce testing cost, instead of performing all tests and determining an exact score, the doctor can perform tests sequentially and stop testing when it is possible to determine the patient's risk class. The problem is to determine the order in which the doctor should perform the tests, so as to minimize expected testing cost. We address the unit-cost case of the Stochastic Score Classification problem, and provide polynomial-time approximation algorithms for adaptive and non-adaptive versions of the problem. We also pose a number of open questions. [ABSTRACT FROM AUTHOR]

We present two new algorithms for convex Mixed Integer Nonlinear Programming (MINLP), both based on the well known Extended Cutting Plane (ECP) algorithm proposed by Weterlund and Petersson. Our first algorithm, Refined Extended Cutting Plane (RECP), incorporates additional cuts to the MILP relaxation of the original problem, obtained by solving linear relaxations of NLP problems considered in the Outer Approximation algorithm. Our second algorithm, Linear Programming based Branch-and-Bound (LP-BB), applies the strategy of generating cuts that is used in RECP, to the linear approximation scheme used by the LP/NLP based Branch-and-Bound algorithm. Our computational results show that RECP and LP-BB are highly competitive with the most popular MINLP algorithms from the literature, while keeping the nice and desirable characteristic of ECP, of being a first-order method. [ABSTRACT FROM AUTHOR]

Sparse tensor best rank-1 approximation (BR1Approx), which is a sparsity generalization of the dense tensor BR1Approx, and is a higher-order extension of the sparse matrix BR1Approx, is one of the most important problems in sparse tensor decomposition and related problems arising from statistics and machine learning. By exploiting the multilinearity as well as the sparsity structure of the problem, four polynomial-time approximation algorithms are proposed, which are easily implemented, of low computational complexity, and can serve as initial procedures for iterative algorithms. In addition, theoretically guaranteed approximation lower bounds are derived for all the algorithms. We provide numerical experiments on synthetic and real data to illustrate the efficiency and effectiveness of the proposed algorithms; in particular, serving as initialization procedures, the approximation algorithms can help in improving the solution quality of iterative algorithms while reducing the computational time. [ABSTRACT FROM AUTHOR]

We discuss sequential stub matching for directed graphs and show that this process can be used to sample simple digraphs with asymptotically equal probability. The process starts with an empty edge set and repeatedly adds edges to it with a certain state-dependent bias until the desired degree sequence is fulfilled, whilst avoiding placing a double edge or self-loop. We show that uniform sampling is achieved in the sparse regime when the maximum degree dmax\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$d_\text {max}$$\end{document} is asymptotically dominated by m1/4\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$m^{1/4}$$\end{document}, where m is the number of edges. The proof is based on deriving various combinatorial estimates related to the number of digraphs with a given degree sequence and controlling concentration of these estimates in large digraphs. This suggests that sequential stub matching can be viewed as a practical algorithm for almost uniform sampling of digraphs. We show that this algorithm can be implemented to feature a linear expected runtime O(m). [ABSTRACT FROM AUTHOR]

They give fixed parameter tractable algorithms for the problem parameterized by various structural parameters. The authors give a greedy loop-free algorithm for the exhaustive generation, a successor algorithm that runs in constant amortized time, among other algorithms, as well as results for the fixed spin generalization of this problem. IWOCA (International Workshop on Combinatorial Algorithms) is an annual conference series covering all aspects of combinatorial algorithms. [Extracted from the article]

A recent paper by Schulze et al. (Math Methods Oper Res 92(1):107–132, 2020) presented the Rectangular Knapsack Problem (Rkp) as a crucial subproblem in the study on the Cardinality-constrained Bi-objective Knapsack Problem (Cbkp). To this end, they started an investigation into its complexity and approximability. The key results are an NP -hardness proof for a more general scenario than Rkp, and a 4.5-approximation for Rkp, raising the question of improvements for either result. In this note we settle both questions conclusively: we show that (a) Rkp is indeed NP -hard in the considered setting (and even in more restricted settings), and (b) there exists both a pseudopolynomial algorithm and a fully-polynomial time approximation scheme (i.e., efficient approximability within any desired ratio α > 1 ) for Rkp. [ABSTRACT FROM AUTHOR]

We present afqn (Approximate Fast Qn), a novel algorithm for approximate computation of the Qn scale estimator in a streaming setting, in the sliding window model. It is well-known that computing the Qn estimator exactly may be too costly for some applications, and the problem is a fortiori exacerbated in the streaming setting, in which the time available to process incoming data stream items is short. In this paper we show how to efficiently and accurately approximate the Qn estimator. As an application, we show the use of afqn for fast detection of outliers in data streams. In particular, the outliers are detected in the sliding window model, with a simple check based on the Qn scale estimator. Extensive experimental results on synthetic and real datasets confirm the validity of our approach by showing up to three times faster updates per second. Our contributions are the following ones: (i) to the best of our knowledge, we present the first approximation algorithm for online computation of the Qn scale estimator in a streaming setting and in the sliding window model; (ii) we show how to take advantage of our UDDSketch algorithm for quantile estimation in order to quickly compute the Qn scale estimator; (iii) as an example of a possible application of the Qn scale estimator, we discuss how to detect outliers in an input data stream. [ABSTRACT FROM AUTHOR]

We consider maximizing a monotone submodular function under a cardinality constraint or a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access to only a small fraction of the data stored in primary memory. We propose the following streaming algorithms taking O(ε− 1) passes: (1) a (1 − e− 1 − ε)-approximation algorithm for the cardinality-constrained problem, (2) a (0.5 − ε)-approximation algorithm for the knapsack-constrained problem. Both of our algorithms run deterministically in O∗(n) time, using O∗(K) space, where n is the size of the ground set and K is the size of the knapsack. Here the term O∗ hides a polynomial of log K and ε− 1. Our streaming algorithms can also be used as fast approximation algorithms. In particular, for the cardinality-constrained problem, our algorithm takes O (n ε − 1 log (ε − 1 log K)) time, improving on the algorithm of Badanidiyuru and Vondrák that takes O (n ε − 1 log (ε − 1 K)) time. [ABSTRACT FROM AUTHOR]

We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include: A (2 + ϵ) -approximation for all-pairs shortest paths in O (log 2 n / ϵ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model. A (1 + ϵ) -approximation for multi-source shortest paths from O (n) sources in O (log 2 n / ϵ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size. Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in O ~ (n 1 / 6) rounds. [ABSTRACT FROM AUTHOR]

We consider a well-studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and a fixed parameter d ≥ 1 , in the maximum diameter-bounded subgraph problem (MaxDBS for short) the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d = 1 , this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n 1 - ϵ , for any ϵ > 0 . Moreover, it is known that, for any d ≥ 2 , it is NP-hard to approximate MaxDBS within a factor n 1 / 2 - ϵ , for any ϵ > 0 . In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems, and several geometric properties of unit disk graphs. [ABSTRACT FROM AUTHOR]

Given a connected graph G = (V , E) , we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k ≥ 4 , no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k ≥ 3 . Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems. [ABSTRACT FROM AUTHOR]

We study the generalized minimum Manhattan network (GMMN) problem: given a set P of pairs of points in the Euclidean plane R 2 , we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the L 1 metric (a so-called Manhattan path) for each pair in P . This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in P , and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach. [ABSTRACT FROM AUTHOR]

In the classic minimum makespan scheduling problem, we are given an input sequence of n jobs with sizes. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we allow the online algorithm to change the assignment of up to k jobs at the end for some limited number k. For m identical machines, Albers and Hellwig (Algorithmica 79(2):598–623, 2017) give tight bounds on the competitive ratio in this model. The precise ratio depends on, and increases with, m. It lies between 4/3 and ≈ 1.4659 . They show that k = O (m) is sufficient to achieve this bound and no k = o (n) can result in a better bound. We study m uniform machines, i.e., machines with different speeds, and show that this setting is strictly harder. For sufficiently large m, there is a δ = Θ (1) such that, for m machines with only two different machine speeds, no online algorithm can achieve a competitive ratio of less than 1.4659 + δ with k = o (n) . We present a new algorithm for the uniform machine setting. Depending on the speeds of the machines, our scheduling algorithm achieves a competitive ratio that lies between 4/3 and ≈ 1.7992 with k = O (m) . We also show that k = Ω (m) is necessary to achieve a competitive ratio below 2. Our algorithm is based on maintaining a specific imbalance with respect to the completion times of the machines, complemented by a bicriteria approximation algorithm that minimizes the makespan and maximizes the average completion time for certain sets of machines. [ABSTRACT FROM AUTHOR]

Unsplittable flow problems cover a wide range of telecommunication and transportation problems and their efficient resolution is key to a number of applications. In this work, we study algorithms that can scale up to large graphs and important numbers of commodities. We present and analyze in detail a heuristic based on the linear relaxation of the problem and randomized rounding. We provide empirical evidence that this approach is competitive with state-of-the-art resolution methods either by its scaling performance or by the quality of its solutions. We provide a variation of the heuristic which has the same approximation factor as the state-of-the-art approximation algorithm. We also derive a tighter analysis for the approximation factor of both the variation and the state-of-the-art algorithm. We introduce a new objective function for the unsplittable flow problem and discuss its differences with the classical congestion objective function. Finally, we discuss the gap in practical performance and theoretical guarantees between all the aforementioned algorithms. [ABSTRACT FROM AUTHOR]

We formulate the sparse classification problem of n samples with p features as a binary convex optimization problem and propose a outer-approximation algorithm to solve it exactly. For sparse logistic regression and sparse SVM, our algorithm finds optimal solutions for n and p in the 10,000 s within minutes. On synthetic data our algorithm achieves perfect support recovery in the large sample regime. Namely, there exists an n 0 such that the algorithm takes a long time to find an optimal solution and does not recover the correct support for n < n 0 , while for n ⩾ n 0 , the algorithm quickly detects all the true features, and does not return any false features. In contrast, while Lasso accurately detects all the true features, it persistently returns incorrect features, even as the number of observations increases. Consequently, on numerous real-world experiments, our outer-approximation algorithms returns sparser classifiers while achieving similar predictive accuracy as Lasso. To support our observations, we analyze conditions on the sample size needed to ensure full support recovery in classification. For k-sparse classification, and under some assumptions on the data generating process, we prove that information-theoretic limitations impose n 0 < C 2 + σ 2 k log (p - k) , for some constant C > 0 . [ABSTRACT FROM AUTHOR]

We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular, we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques toward predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize. [ABSTRACT FROM AUTHOR]

We study a security game over a network played between a defender and kattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of λ nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizing defense-optimal networks which allow for the best equilibrium defense ratio; this is the ratio of k over the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for λ constantly close to 1 or n. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is NP -hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the Price of Defense for any λ ; this is the worst equilibrium defense ratio over all graphs. [ABSTRACT FROM AUTHOR]

This paper introduces the d-distance matching problem, in which we are given a bipartite graph G = (S , T ; E) with S = { s 1 , ⋯ , s n } , a weight function on the edges and an integer d ∈ Z + . The goal is to find a maximum-weight subset M ⊆ E of the edges satisfying the following two conditions: (i) the degree of every node of S is at most one in M, (ii) if s i t , s j t ∈ M , then | j - i | ≥ d . This question arises naturally, for example, in various scheduling problems. We show that the problem is NP-complete in general and admits a simple 3-approximation. We give an FPT algorithm parameterized by d and also show that the case when the size of T is constant can be solved in polynomial time. From an approximability point of view, we show that the integrality gap of the natural integer programming model is at most 2 - 1 2 d - 1 , and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial (2 - 1 d) -approximation algorithm is also presented. Several greedy approaches are considered, and a local search algorithm is described that achieves an approximation ratio of 3 / 2 + ϵ for any constant ϵ > 0 in the unweighted case. The novel approaches used in the analysis of the integrality gap and the approximation ratio of locally optimal solutions might be of independent combinatorial interest. [ABSTRACT FROM AUTHOR]

A new multiple-point statistics algorithm, SparseSim, is developed based on sparse approximation algorithm, which has wide applications for stochastic simulation in the field of geosciences and beyond. The current version is described in the context of reservoir characterization, which includes well and seismic data integration. In sparse approximation, a model image is represented as weighted linear combination of columns of the dictionary matrix. For this purpose, a parsimonious subset of the dictionary columns and their corresponding weights are selected using sparse coding methods. The dictionary is obtained by dictionary learning algorithms trained over and adapted for specific types of model images in the training set. Based on the sparse approximation algorithm, the approximated model image is generated by multiplication of the dictionary and the weight matrices. Intuitively, stochastic simulation of the coefficient (weight) matrix will lead to generation of new stochastic realizations. The SparseSim algorithm, as represented in this paper, works based on extracting the trend for nonzero elements in the significant rows of the weight matrix, and it is proposed under two general schemes: stochastically simulating the details of the training image or stochastically simulating both the details and the mean value of the training image. It is shown in this paper that under both schemes the generated realizations, while stochastically distinct, are similar to each other and to the training image. Different aspects of the SparseSim algorithm such as SparseSim in 3D, SparseSim in different scales, and data conditioning are also discussed. [ABSTRACT FROM AUTHOR]

In this paper, we work on the scheduling problem with active time model. We have a set of preemptive jobs with integral release times, deadlines and required processing lengths, while the preemption of jobs is only allowed at integral time points. We have a single machine that can process at most g distinct job units at any given time unit when the machine is switched on. The objective is to find a schedule that completes all jobs within their timing constraints and minimizes the time when the machine is on, i.e., the active time. This problem has been studied by Chang et al. where they proposed an LP rounding approach which gives a 2-approximation solution. In this paper, we also give a 2-approximation algorithm based on LP rounding approach with a different rounding technique and analysis. Finally, we give a new linear programming formulation for which we conjecture that the integrality gap is 5/3, which might bring new hope for beating the barrier of 2 for the approximation ratio. [ABSTRACT FROM AUTHOR]

Uncertainty about data appears in many real-world applications and an important issue is how to manage, analyze and solve optimization problems over such data. An important tool for data analysis is clustering. When the data set is uncertain, we can model them as a set of probabilistic points each formalized as a probability distribution function which describes the possible locations of the points. In this paper, we study k-center problem for probabilistic points in a general metric space. First, we present a fast greedy approximation algorithm that builds k centers using a farthest-first traversal in k iterations. This algorithm improves the previous approximation factor of the unrestricted assigned k-center problem from 10 (see [1]) to 6. Next, we restrict the centers to be selected from all the probabilistic locations of the given points and we show that an optimal solution for this restricted setting is a 2-approximation factor solution for an optimal solution of the assigned k-center problem with expected distance assignment. Using this idea, we improve the approximation factor of the unrestricted assigned k-center problem to 4 by increasing the running time. The algorithm also runs in polynomial time when k is a constant. Additionally, we implement our algorithms on three real data sets. The experimental results show that in practice the approximation factors of our algorithms are better than in theory for these data sets. Also we compare the results of our algorithm with the previous works and discuss about the achieved results. At the end, we present our theoretical results for probabilistic k-median clustering. [ABSTRACT FROM AUTHOR]