Search

This paper introduces the d-distanceb-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, an integer d ∈ Z + and a degree bound function b : S ∪ T → Z + . The goal is to find a maximum-weight subset M ⊆ E of the edges satisfying the following two conditions: (1) the degree of each node v ∈ S ∪ T is at most b(v) in M, (2) if s i t , s j t ∈ M , then | i - j | ≥ d . In the cyclic version of the problem, the nodes in S are considered to be in cyclic order. We get back the (cyclic)d-distance matching problem when b (s) = 1 for s ∈ S and b (t) = ∞ for t ∈ T . We prove that the d-distance matching problem is APX-hard, even in the unweighted case. We show that 2 - 1 d is a tight upper bound on the integrality gap of the natural integer programming model for the cyclic d-distance b-matching problem provided that (2 d - 1) divides the size of S. For the non-cyclic case, the integrality gap is shown to be at most (2 - 2 d) . The proofs give approximation algorithms with guarantees matching these bounds, and also improve the best known algorithms for the (cyclic) d-distance matching problem. In a related problem, our goal is to find a permutation of S maximizing the weight of the optimal d-distance b-matching. This problem can be solved in polynomial time for the (cyclic) d-distance matching problem — even though the (cyclic) d-distance matching problem itself is NP-hard and also hard to approximate arbitrarily. For (cyclic) d-distance b-matchings, however, we prove that finding the best permutation is NP-hard, even if b ≡ 2 or d = 2 , and we give e-approximation algorithms. [ABSTRACT FROM AUTHOR]

This study addresses the energy efficiency challenge in cloud data centers by examining the Virtual Machine Placement (VMP) problem. VMP involves mapping virtual machines (VMs) to physical machines (PMs) under capacity constraints. The paper focuses on the bin packing with linear usage cost (BPLUC) variant of bin packing, which includes fixed and variable costs in the calculation of the cost of a used bin. We prove that every approximation algorithm for the bin and vector bin packing can be used for BPLUC and VBPLUC, respectively. We propose a more power-efficient approach to VMP by applying a vector bin packing algorithm to minimize power consumption in data centers. We test the proposed algorithm on various synthetic and real workloads, and the experimental results demonstrate that it is more power-efficient than existing algorithms for VMP. The findings suggest that the proposed algorithm has significant implications for energy-efficient strategies in cloud data centers. Generally, this study makes contributes to the development of energy-efficient approaches to VMP that can help reduce power consumption and improve the sustainability of cloud data centers. [ABSTRACT FROM AUTHOR]

We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The previous best-known approximation ratio using ordinal preferences is 2 - 1 / n by Aziz et al. [AAAI 2017]. We improve this result by giving a deterministic 5/3-approximation algorithm that determines an allocation sequence of agents, according to which items are allocated one by one. By a tighter analysis, we show that for n = 2 and 3, our algorithm achieves better approximation ratios, and is actually optimal. We also consider the setting with strategic agents, where agents may misreport their preferences to manipulate the outcome. We first provide a strategyproof O (log (m / n)) -approximation consecutive picking algorithm, and then improve the approximation ratio to O (log n) by a randomized algorithm. Both algorithms only use the ordinal preferences of agents. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods. [ABSTRACT FROM AUTHOR]

We consider the robust version of the classic k-center clustering problem, where we wish to remove up to z points (outliers), so as to be able to cluster the remaining points in k clusters with minimum maximum radius. We study such a problem under the fully dynamic adversarial model, where points can be inserted or deleted arbitrarily. In this setting, the main goal is to design algorithms that maintain a high quality solution at any point in time, while requiring a "small" amortized cost, i.e. a "small" number of operations per insertion or deletion, on average. In our work, we provide the first constant bi-criteria approximation algorithm for such a problem with its amortized cost being independent of both z and the size of the current input. We also complement our positive result with a lower bound showing that any constant (non bi-criteria) approximation algorithm has amortized cost at least linear in z. Finally, we conduct an in-depth experimental analysis of our algorithm on Twitter, Flickr, and Air-Quality datasets showing the effectiveness of our approach. [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]

In this paper, we study restricted variations of the following obnoxious facility location problem in the plane: locate k new obnoxious facilities amidst n ordered demand points (existing facility sites) in the plane so that none of the existing facility sites are affected. We study this problem in two restricted settings. The obnoxious facilities are constrained to be centered on (i) a predetermined horizontal line segment pq ¯ , and (ii) the boundary arc of a predetermined disk C . For the problem in (i), we first give an (1 - ϵ) -approximation algorithm that runs in O (n + k) log | | p q | | 2 (k - 1) ϵ time, where ϵ > 0 and ||pq|| is the length of pq ¯ . We then propose two exact polynomial time algorithms, one based on doing binary search on all candidates and the other with the parametric search technique of Megiddo (J ACM 30:852–865, 1983); that will take O (n k) 2 time and O (n + k) 2 time respectively. Continuing further, using the improved parametric technique, we give an O (n log n) -time algorithm for k = 2 . We also show that the (1 - ϵ) -approximation algorithm of (i) can be easily adapted to solve the problem (ii) with an extra multiplicative factor of n in the running time. Finally, we give a O (n 3 k) -time dynamic programming solution to the min-sum obnoxious facility location problem restricted to a line segment where the demand points are associated with weights, and the goal is to minimize the sum of the weights of the points covered. [ABSTRACT FROM AUTHOR]

An algorithm for automatic approximation of the time dependence x(t) is built for the observed coordinate of the coronal mass ejection (CME) front from the admissible starting point to the first appearance in the field of view of the LASCO coronagraph and further, up to a heliocentric distance of ~25 solar radii (RS). In the region from the starting point to the first appearance of the CME, two sections are assumed, with uniform (impulsive) acceleration and with uniform motion; then, the motion is approximated by observations. At the beginning of the approximation, either the CME start time is found through the appearance of certain frequencies of radio emissions (RSTN data) and type II and IV radio emissions (sequence characteristics are determined by machine learning), or the start time is determined by averaging over the allowable takeoff area; then the polynomial-ballistic model is optimized. The first and second derivatives x(t) determine the speed and acceleration of the CME at any point of its trajectory. Such an algorithm is necessary to obtain the most accurate kinematic characteristics of CMEs, which can allow one to study the physical, spatial, and temporal relationships between flares and CMEs in all their diversity. Widely used approximation techniques simplify the real CME trajectories x(t), thereby possibly discarding important features of the CME kinematics and flare development in the posteruptive phase. The algorithm was trained and tested on 17 solar flares and associated CMEs, which are known for their powerful proton events with proton energies greater than 300 MeV. The rate of the first occurrence of CMEs turned out to be different from the average rate given in the LASCO catalog, which is important for estimating the energy of flares and CMEs. In 7 out of 17 events, there was acceleration only in the impulsive phase (and then deceleration), while acceleration in the impulsive and posteruptive phases occurred in 10 events. In 4 out of 17 events, CME velocities greater than 2000 km/s were reached at a distance of 20RS. The accuracy of determining the kinematic characteristics of CMEs can be improved by using additional observations, for example, SDO AIA in the September 10, 2017 event. [ABSTRACT FROM AUTHOR]

We introduce a dynamical system to the problem of finding zeros of the sum of two maximally monotone operators. We investigate the existence, uniqueness and extendability of solutions to this dynamical system in a Hilbert space. We prove that the trajectories of the proposed dynamical system converge strongly to a primal–dual solution of the considered problem. Under explicit time discretization of the dynamical system we obtain the best approximation algorithm for solving coupled monotone inclusion problem. [ABSTRACT FROM AUTHOR]

In this paper, the first fixed-ratio approximation algorithms are proposed for a series of asymmetric settings of well-known combinatorial routing problems. Among them are the Steiner cycle problem, the prize-collecting traveling salesman problem, the minimum cost cycle cover problem by a bounded number of cycles, etc. Almost all of the proposed algorithms rely on original reductions of the considered problems to auxiliary instances of the asymmetric traveling salesman problem and employ the breakthrough approximation results for this problem obtained recently by O. Svensson, J. Tarnawski, L. Végh, V. Traub, and J. Vygen. On the other hand, approximation of the cycle cover problem was proved by applying a deeper extension of their approach. [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]

The gate-based model is one of the leading quantum computing paradigms for representing quantum circuits. Within this paradigm, a quantum algorithm is expressed in terms of a set of quantum gates that are executed on the quantum hardware over time, subject to a number of constraints whose satisfaction must be guaranteed before running the circuit, to allow for feasible execution. The need to guarantee the previous feasibility condition gives rise to the Quantum Circuit Compilation Problem (QCCP). The QCCP has been demonstrated to be NP-Complete, and can be considered as a Planning and Scheduling problem. In this paper, we consider quantum compilation instances deriving from the general Quantum Approximation Optimization Algorithm (QAOA), applied to the MaxCut problem, devised to be executed on Noisy Intermediate Scale Quantum (NISQ) hardware architectures. More specifically, in addition to the basic QCCP version, we also tackle other variants of the same problem such as the QCCP-X (QCCP with crosstalk constraints), the QCCP-V (QCCP with variable qubit state initialization), as well as the QCCP-VX that includes both previous variants. All problem variants are solved using genetic algorithms. We perform an experimental study across a conventional set of instances taken from the literature, and show that the proposed genetic algorithm, termed G A VX , outperforms previous approaches in the literature. [ABSTRACT FROM AUTHOR]

Simple heuristics for (combinatorial) optimization problems often show a remarkable performance in practice. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many (combinatorial) optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained in recent years, where random shortest path metrics generated from dense graphs (either complete graphs or Erdős–Rényi random graphs) have been used so far. In this paper we extend these findings to sparse graphs, with a focus on sparse graphs with 'fast growing cut sizes', i.e. graphs for which | δ (U) | = Ω (| U | ε) for some constant ε ∈ (0 , 1) for all subsets U of the vertices, where δ (U) is the set of edges connecting U to the remaining vertices. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances generated from a sparse graph with fast growing cut sizes, we prove that the greedy heuristic for the minimum distance maximum matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, for instances generated from an arbitrary sparse graph, we show that the 2-opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio. [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 present deterministic algorithms for maintaining a (3 / 2 + ϵ) and (2 + ϵ) -approximate maximum matching in a fully dynamic graph with worst-case update times O ^ (n) and O ~ (1) respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio (2 - δ) (for any δ > 0 ) and (2 + ϵ) were both shown by Roghani et al. (Beating the folklore algorithm for dynamic matching, 2021) with update times O (n 3 / 4) and O ϵ (n) respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are O ϵ (n) and O ~ (1) which were shown in Bernstein and Stein (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, 2016) and Bhattacharya and Kiss (in: 48th international colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021) respectively. The algorithm achieving (3 / 2 + ϵ) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein (in: International colloquium on automata, languages, and programming, Springer, Berlin, 2015). Say that H is a (α , δ) -approximate matching sparsifier if at all times H satisfies that μ (H) · α + δ · n ≥ μ (G) (define (α , δ) -approximation similarly for matchings). We show how to maintain a locally damaged version of the EDCS which is a (3 / 2 + ϵ , δ) -approximate matching sparsifier. We further show how to reduce the maintenance of an α -approximate maximum matching to the maintenance of an (α , δ) -approximate maximum matching building based on an observation of Assadi et al. (in: Proceedings of the twenty-seventh annual (ACM-SIAM) symposium on discrete algorithms, (SODA) 2016, Arlington, VA, USA, January 10–12, 2016). Our reduction requires an update time blow-up of O ^ (1) or O ~ (1) and is deterministic or randomized against an adaptive adversary respectively. To achieve (2 + ϵ) -approximation we improve on the update time guarantee of an algorithm of Bhattacharya and Kiss (in: 48th International colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021). In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak (in: Proceedings of the twenty-seventh annual ACM symposium on theory of computing, 2017) and Bernstein et al. (Fully-dynamic graph sparsifiers against an adaptive adversary, 2020) which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time. [ABSTRACT FROM AUTHOR]

Due to its fast training speed and powerful approximation capabilities, the extreme learning machine (ELM) has generated a lot of attention in recent years. However, the basic ELM still has some drawbacks, such as the tendency to over-fitting and the susceptibility to noisy data. By adding a regularization term to the basic ELM, the regularized extreme learning machine (R-ELM) can dramatically improve its generalization and stability. In the R-ELM, choosing an appropriate regularization parameter is critical since it can regulate the fitting and generalization capabilities of the model. In this paper, we propose the regularized functional extreme learning machine (RF-ELM), which employs the regularization functional instead of a preset regularization parameter for adaptively choosing appropriate regularization parameters. The regularization functional is defined according to output weights, and the successive approximation iterative algorithm is utilized to solve the output weights so that we can get their values simultaneously at each iteration step. We also developed a parallel version of RF-ELM (PRF-ELM) to deal with big data tasks. Furthermore, the analysis of convexity and convergence ensures the validity of the model training. Finally, the experiments on the function approximation and the UCI repository with or without noise data demonstrate the superiority and competitiveness of our proposed models. [ABSTRACT FROM AUTHOR]

We study the following scheduling problem with transportation. Given a set of n jobs that need to be processed on a single machine, we need to deliver the finished jobs to one of the two destinations using a single transporter. The goal is to minimize the time that all the jobs are delivered to their destination, such that the transporter returns. We propose a 11 / 6 + ε -approximation algorithm which improves upon the best-known approximation ratio of 2. [ABSTRACT FROM AUTHOR]

We consider batch scheduling on m machines to minimize the makespan. Each job has a given set of machines to be assigned. Each machine can process several jobs simultaneously as a batch, and the machines may have different batch capacities. We study two models: (i) scheduling on equal-speed batch machines under a nested processing set restriction, where the machines have the same processing speed, and (ii) scheduling on uniform batch machines under a tree-hierarchical processing set restriction, where the machines have different processing speeds. For both models we design polynomial-time approximation algorithms to solve them. The algorithms have a worst-case ratio of 2 for non-identical batch capacities and a worst-case ratio of 2 - 1 / m for identical batch capacities. [ABSTRACT FROM AUTHOR]

We study a generalization of the well-known traveling salesman problem in a metric space, in which each city is associated with a release time. The salesman has to visit each city at or after its release time. There exists a naive 5/2-approximation algorithm where the salesman simply starts to route the network after all cities are released. Interestingly, this bound has never been improved for more than two decades. In this paper, we revisit the problem and achieve the following results. First, we devise an approximation algorithm with performance ratio less than 5/2 when the number of distinct release times is fixed. Then, we analyze a natural class of algorithms and show that no performance ratio better than 5/2 is possible unless the Metric TSP can be approximated with a ratio strictly less than 3/2, which is a well-known longstanding open question. Finally, we consider a special case where the graph has a heavy edge and present an approximation algorithm with performance ratio less than 5/2. [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]

This paper presents a QR decomposition based low-rank approximation algorithm for training and prediction in Gaussian process regression. Conventional low-rank methods like FITC, Nyström, etc., rely on low-rank approximations to the full kernel matrix that are derived from a set of representative data points. Training with FITC involves the selection of these representative points and is computationally intensive when the dimension of the dataset is large. Prediction accuracy of Nyström suffers when the number of representative points is small or when the length scale is small. The algorithm proposed here uses the thin QR decomposition of the low-rank matrix used in the Nyström approximation. We show that the marginal likelihood and its derivatives needed for training can be split into the subspace belonging to that approximation and its orthogonal complement. During prediction, we further restrict the target vectors into this subspace and thus eliminate the numerical error caused by very low noise variance. Use of the QR factorization improves the training and prediction performance. Experiments on real and synthetic data show that our approach is more accurate and faster than conventional methods. Our algorithm performs well at low length scales and achieves the prediction accuracy comparable to the full kernel matrix approach even for low rank approximations, without the need to optimize the representative points. This results in a simpler and faster approximation that could be used to scale Gaussian process regression to large datasets. [ABSTRACT FROM AUTHOR]

The minimum weighted vertex cover (MWVC) problem is to find a subset of vertices that can cover all the edges of the network and minimize the sum of the vertex weights in the vertex subset. MWVC is a generalization of the minimum vertex cover (MVC) problem and can be regarded as a combinatorial optimization problem. This paper proposes an evolutionary algorithm based on the snowdrift game to solve the MWVC problem. We use the evolutionary algorithm framework, and the snowdrift game is combined to construct and improve the initial solution. First, the network's vertex is regarded as an intelligent agent, and each vertex and its neighbors play a snowdrift game to form an initial solution. Then local search and global search are used to improve the initial solution. The solution is improved according to the proposed score function in the local search stage to obtain a better MWVC solution. The evolutionary algorithm is used in the global search stage to escape the local optimum. Experiments on different networks show that the proposed algorithm are effective on weighted networks. [ABSTRACT FROM AUTHOR]

We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as building blocks, we construct a triangulation scheme called crossing swords that requires at most - times the number of simplices in any optimal triangulation. In other words, we derive an approximation algorithm for the optimal triangulation problem. We also show that crossing swords yields optimal triangulations in the case that each simplex has at least one axis-parallel edge. Furthermore, we present approximation guarantees for other well-known triangulation schemes, namely for the red refinement and longest-edge bisection strategies as well as for a generalized version of K1-triangulations. Thereby, we are able to show that our novel approach dominates previous triangulation schemes from the literature, which is underlined by illustrative numerical examples. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a collection P of vertex-disjoint (simple) paths is called a path cover of G if every vertex v ∈ V is contained in exactly one path of P . The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In this paper, we introduce generalizations of PC, where each path is associated with a weight (cost or profit). Our problem, Minimum (Maximum) Weighted Path Cover [MinPC (MaxPC)], is defined as follows: Let U = { 0 , 1 , ⋯ , n - 1 } . Given a graph G = (V , E) and a weight function f : U → R ∪ { + ∞ , - ∞ } that defines a weight for each path based on its length, the objective of MinPC (MaxPC) is to find a path cover P of G such that the total weight of the paths in P is minimized (maximized). Let L be a subset of U, and P L be the set of paths such that each path is of length ℓ ∈ L . We consider Min P L PC with binary cost, i.e., the cost function is f (ℓ) = 1 if ℓ ∈ L ; otherwise, f (ℓ) = 0 . We also consider Max P L PC with f (ℓ) = ℓ + 1 , if ℓ ∈ L ; otherwise, f (ℓ) = 0 . Many well-known graph theoretic problems such as the Hamiltonian Path and the Maximum Matching problems can be modeled using Min P L PC and Max P L PC. In this paper, we first show that deciding whether Min P { 0 , 1 , 2 } PC has a 0-weight solution is NP-complete for planar bipartite graphs of maximum degree three, and consequently, (i) for any constant σ ≥ 1 , there is no polynomial-time approximation algorithm with approximation ratio σ for Min P { 0 , 1 , 2 } PC unless P = NP, and (ii) Max P { 3 , ⋯ , n - 1 } PC is NP-hard for the same graph class. Next, we present a polynomial-time algorithm for Min P { 0 , 1 , ⋯ , k } PC on graphs with bounded treewidth for a fixed k. Lastly, we present a 4-approximation algorithm for Max P { 3 , ⋯ , n - 1 } PC, which becomes a 2.5-approximation algorithm for subcubic graphs. [ABSTRACT FROM AUTHOR]

We consider the max hypergraph 3-cut problem with limited unbalance (MH3C-LU). The objective is to divide the vertex set of an edge-weighted hypergraph H = (V , E , w) into three disjoint subsets V 1 , V 2 , and V 3 such that the sum of edge weights cross different parts is maximized subject to | | V i | - | V l | | ≤ B ( ∀ i ≠ l ∈ { 1 , 2 , 3 } ) for a given parameter B. This problem is NP-hard because it includes some well-known problems like the max 3-section problem and the max 3-cut problem as special cases. We formulate the MH3C-LU as a ternary quadratic program and present a randomized approximation algorithm based on the complex semidefinite programming relaxation technique. [ABSTRACT FROM AUTHOR]

In this paper, we propose and investigate the individually fair k-center with outliers (IFkCO). In the IFkCO, we are given an n-sized vertex set in a metric space, as well as integers k and q. At most k vertices can be selected as the centers and at most q vertices can be selected as the outliers. The centers are selected to serve all the not-an-outlier (i.e., served) vertices. The so-called individual fairness constraint restricts that every served vertex must have a selected center not too far way. More precisely, it is supposed that there exists at least one center among its ⌈ (n - q) / k ⌉ closest neighbors for every served vertex. Because every center serves (n - q) / k vertices on the average. The objective is to select centers and outliers, assign every served vertex to some center, such that the maximum fairness ratio over all served vertices is minimized, where the fairness ratio of a vertex is defined as the ratio between its distance with the assigned center and its distance with a ⌈ (n - q) / k ⌉ th closest neighbor. As our main contribution, a 4-approximation algorithm is presented, based on which we develop an improved algorithm from a practical perspective. Extensive experiment results on both synthetic datasets and real-world datasets are presented to illustrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Matrix decomposition is a widely used tool in machine learning with many applications such as dimension reduction or visualization. In this paper we consider decomposing X, a matrix of size n × m , to a product WS where we require that S, a matrix of size n × k , needs to have consecutive ones property. More specifically, we require that each row of S needs to be in the form of 0 , ... , 0 , 1 , ... , 1 , 0 , ... , 0 . Such decompositions are particularly meaningful if X is a matrix where each row represents a time series; in such a case the ones in each row in S represent a time segment. We show that the optimization problem is inapproximable. To solve the problem we propose 5 different algorithms. The first two algorithms are based on solving iteratively S while keeping W fixed and then solving W while keeping S fixed. The next two algorithms are based on greedily optimizing a single row in S and the corresponding column in W. The last algorithm first finds the optimal decomposition of with 2 k - 1 non-overlapping rows, and then greedily combines the rows until k rows remain. We compare the algorithms experimentally, focusing on the quality of the decomposition as well as the computational time. We show experimentally that our algorithms yield interpretable results in practical time. [ABSTRACT FROM AUTHOR]

We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1 polytopes and half-integral polytopes. [ABSTRACT FROM AUTHOR]

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of computational complexity. Notice that every n-vertex sum graph can be represented by a sorted list of n positive integers where edge queries can be answered in O (log n) time. Therefore, upper-bounding the numbers used as vertex labels also upper-bounds the space complexity of storing the graph in the database. We show that every n-vertex, m-edge, d-degenerate graph can be made a sum graph by adding at most m isolated vertices to it, such that the largest numbers used as vertex labels grows as O (n 2 d) . This enables us to store the graph using O (m log n) bits of memory. For sparse graphs (graphs with O (n) edges), this matches the trivial lower bound of Ω (n log n) . As planar graphs and forests have constant degeneracy, our result implies an upper bound of O (n 2) on their label numbers. The previously best known upper bound on the numbers needed for labelling general graphs with the minimum number of isolated vertices was O (4 n) , due to Kratochvíl, Miller & Nguyen (2001). Furthermore, their proof was existential, whereas our labelling can be constructed in polynomial time. [ABSTRACT FROM AUTHOR]

In the Strip Packing problem, we are given a vertical half-strip [ 0 , W ] × [ 0 , + ∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. It is NP-hard to approximate this problem within a factor (3 / 2 - ε) for any constant ε > 0 by a simple reduction from the Partition problem, while the current best approximation factor for it is (5 / 3 + ε) . It seems plausible that Strip Packing admits a (3 / 2 + ε) -approximation. We make progress in that direction by achieving such tight approximation guarantees for a special family of instances, which we call skewed instances. As standard in the area, for a given constant parameter δ > 0 , we call large the rectangles with width at least δ W and height at least δ O P T , and skewed the remaining rectangles. If all the rectangles in the input are large, then one can easily compute the optimal packing in polynomial time (since the input can contain only a constant number of rectangles). We consider the complementary case where all the rectangles are skewed. This second case retains a large part of the complexity of the original problem; in particular, the skewed case is still NP-hard to approximate within a factor (3 / 2 - ε) , and we provide an (almost) tight (3 / 2 + ε) -approximation algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a combined method for the equivalent circuit parameters estimation of cage induction motors. The method is based on dual usage of the particle swarm optimization algorithm and the approximation of rotor parameters as a function of the speed, due to the influence of the skin effect. The approximation of rotor parameters as a function of the speed is not directly applied in the parameters estimation algorithm, but it is used to obtain the torque-speed characteristics of cage induction motors. The first stage of the optimization includes the estimation of equivalent circuit parameters of a motor for the nominal operating mode, while the rotor parameters at the start of the motor are estimated in the second stage of the optimization. These parameters are obtained as a result of minimizing the error between the calculated and the manufacture data. The proposed method is applied on eight two-pole induction motors with different rated powers, energy efficiency class IE3, manufactured by ABB. The results are verified by comparing the obtained torque-speed characteristics with the corresponding characteristics provided by the manufacturer (i.e., ABB) using the MotSize program. It is shown that the torque-speed characteristics obtained by the proposed method are in a good agreement with the characteristics given by the manufacturer. Also, the value of the mean absolute relative error does not exceed 5% for all considered motors. [ABSTRACT FROM AUTHOR]

In malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. In this setting, jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job j on a set of allocated machines S depends on the total speed of S with respect to j. For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than e e - 1 , unless P = N P . On the positive side, we present polynomial-time algorithms with approximation ratios 2 e e - 1 for machines with unrelated speeds, 3 for machines with uniform speeds, and 7/3 for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding. They result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of 1 + φ for unrelated speeds (φ is the golden ratio) and 2 for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms for a variant where we determine the effective speed of a set of allocated machines based on the L p norm of their speeds. [ABSTRACT FROM AUTHOR]

Constrained partially observable Markov decision processes (CPOMDPs) have been used to model various real-world phenomena. However, they are notoriously difficult to solve to optimality, and there exist only a few approximation methods for obtaining high-quality solutions. In this study, grid-based approximations are used in combination with linear programming (LP) models to generate approximate policies for CPOMDPs. A detailed numerical study is conducted with six CPOMDP problem instances considering both their finite and infinite horizon formulations. The quality of approximation algorithms for solving unconstrained POMDP problems is established through a comparative analysis with exact solution methods. Then, the performance of the LP-based CPOMDP solution approaches for varying budget levels is evaluated. Finally, the flexibility of LP-based approaches is demonstrated by applying deterministic policy constraints, and a detailed investigation into their impact on rewards and CPU run time is provided. For most of the finite horizon problems, deterministic policy constraints are found to have little impact on expected reward, but they introduce a significant increase to CPU run time. For infinite horizon problems, the reverse is observed: deterministic policies tend to yield lower expected total rewards than their stochastic counterparts, but the impact of deterministic constraints on CPU run time is negligible in this case. Overall, these results demonstrate that LP models can effectively generate approximate policies for both finite and infinite horizon problems while providing the flexibility to incorporate various additional constraints into the underlying model. [ABSTRACT FROM AUTHOR]

In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be N P -hard, while also proving N P -hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task setting. [ABSTRACT FROM AUTHOR]

Based on results of experiments, we analyze the efficiency of some exact and approximation algorithms for a semi-supervised graph 2-clustering problem. [ABSTRACT FROM AUTHOR]

In this paper, we give an algorithm that finds an ϵ -approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the rank of the quadratic function and the number of integer variables are fixed. The running time of the algorithm is expected unless P = NP. In order to design this algorithm we introduce the novel concepts of spherical form MIQP and of aligned vectors, and we provide a number of results of independent interest. In particular, we give a strongly polynomial algorithm to find a symmetric decomposition of a matrix, and show a related result on simultaneous diagonalization of matrices. [ABSTRACT FROM AUTHOR]

We study algorithmic Bayesian persuasion problems in which the principal (a.k.a. the sender) has to persuade multiple agents (a.k.a. receivers) by using public communication channels. Specifically, our model follows the multi-receiver model with no inter-agent externalities introduced by Arieli and Babichenko (J Econ Theory 182:185–217, 2019). It is known that the problem of computing a sender-optimal public persuasive signaling scheme is not approximable even in simple settings. Therefore, prior works usually focus on determining restricted classes of the problem for which efficient approximation is possible. Typically, positive results in this space amounts to finding bi-criteria approximation algorithms yielding an almost optimal and almost persuasive solution in polynomial time. In this paper, we take a different perspective and study the persuasion problem in the general setting where the space of the states of nature, the action space of the receivers, and the utility function of the sender can be arbitrary. We fully characterize the computational complexity of computing a bi-criteria approximation of an optimal public signaling scheme in such settings. In particular, we show that, assuming the Exponential Time Hypothesis, solving this problem requires at least a quasi-polynomial number of steps even in instances with simple utility functions and binary action spaces such as an election with the k-voting rule. In doing so, we prove that a relaxed version of the Maximum Feasible Subsystem of Linear Inequalities problem requires at least quasi-polynomial time to be solved. Finally, we close the gap by providing a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, under mild assumptions, yields a QPTAS. [ABSTRACT FROM AUTHOR]

In Two-dimensional Bin Packing (2BP), we are given n rectangles as input and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. 2BP admits no APTAS and the current best approximation ratio is 1.406 by Bansal and Khan (ACM-SIAM symposium on discrete algorithms (SODA), pp 13–25, 2014. https://doi.org/10.1137/1.9781611973402.2). A well-studied variant of 2BP is Guillotine Two-dimensional Bin Packing (G2BP), where rectangles must be packed in such a way that every rectangle in the packing can be obtained by applying a sequence of end-to-end axis-parallel cuts, also called guillotine cuts. Bansal et al. (Symposium on foundations of computer science (FOCS). IEEE, pp 657–666, 2005. https://doi.org/10.1109/SFCS.2005.10) gave an APTAS for G2BP. Let λ be the smallest constant such that for every set I of items, the number of bins in the optimal solution to G2BP for I is upper bounded by λ opt (I) + c , where opt (I) is the number of bins in the optimal solution to 2BP for I and c is a constant. It is known that 4 / 3 ≤ λ ≤ 1.692 . Bansal and Khan (2014) conjectured that λ = 4 / 3 . The conjecture, if true, will imply a (4 / 3 + ε) -approximation algorithm for 2BP. Given a small constant δ > 0 , a rectangle is called large if both its height and width are at least δ , else it is called skewed. We make progress towards the conjecture by showing that λ = 4 / 3 when all input rectangles are skewed. We also give an APTAS for 2BP for skewed items, though general 2BP does not admit an APTAS. [ABSTRACT FROM AUTHOR]

In this paper, we propose some new semidefinite relaxations for a class of nonconvex complex quadratic programming problems, which widely appear in the areas of signal processing and power system. By deriving new valid constraints to the matrix variables in the lifted space, we derive some enhanced semidefinite relaxations of the complex quadratic programming problems. Then, we compare the proposed semidefinite relaxations with existing ones, and show that the newly proposed semidefinite relaxations could be strictly tighter than the previous ones. Moreover, the proposed semidefinite relaxations can be applied to more general cases of complex quadratic programming problems, whereas the previous ones are only designed for special cases. Numerical results indicate that the proposed semidefinite relaxations not only provide tighter relaxation bounds, but also improve some existing approximation algorithms by finding better sub-optimal solutions. [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]

Feature selection is an essential task in the field of machine learning, data mining, and pattern recognition, primarily, when we deal with a large number of features. Feature selection assists in enhancing prediction accuracy, reducing computation time, and creating more comprehensible models. In feature selection, each feature has two possibilities, either it would be taken for computation or not, which implies for n number of features, there are 2 n possible feature subsets. So, identifying a relevant feature subset in a reasonable amount of time is an NP-hard problem, but by using an approximation algorithm, a near-optimal solution can be achieved. However, many of the feature selection algorithms use a sequential search strategy to select relevant features, which adds or removes features from the dataset sequentially and leads to trapped into a local optimum solution. In this paper, we propose a novel clustering-based hybrid feature selection approach using ant colony optimization that selects features randomly and measures the qualities of features by K-means clustering in terms of silhouette index and Laplacian score. The proposed feature selection approach allows random selection of features, which allows a better exploration of feature space and thus avoids the problem of being trapped in a local optimal solution, and generates a global optimal solution. The same is verified when compared with another state-of-the-art method. [ABSTRACT FROM AUTHOR]

In wireless sensor networks (WSNs), the virtual backbone (VB) consists of a subset of nodes, which are responsible for routing tasks. Fault-tolerant VBs are desirable for overcoming the effects of node or link failure in WSNs. Usually, a homogeneous WSN (VB) is abstracted as a unit disk graph (UDG) (connected dominating set(CDS)). This paper introduces the concept of a fault-tolerant CDS in a UDG called a ((2, 2), m)-CDS, which is different from a traditional fault-tolerant CDS ((k, m)-CDS). A ((2, 2), m)-CDS can still function even if one edge or one node fails, which implies that it possesses fault-tolerant properties for both nodes and edges, in contrast to traditional (k, m)-CDSs, which possess fault tolerance only for nodes. Then, we propose a 5 α -approximation algorithm for computing a ((2, 2), m)-CDS, where α is the performance ratio for computing a (2, m) -CDS, and analyze its time complexity. In simulations, we compare our algorithm with an existing algorithm for fault-tolerant CDS construction based on CDS size. From the simulations, we find that our algorithm outperforms its competitor in constructing a quality VB. [ABSTRACT FROM AUTHOR]

We consider scheduling monotonic moldable tasks on multiple platforms, where each platform contains a set of processors. A moldable task can be split into several pieces of equal size and processed simultaneously on multiple processors. Tasks are not allowed to be processed spanning over platforms. This scheduling model has many applications, ranging from parallel computing to the berth and quay crane allocation and the workforce assignment problem. We develop several approximation algorithms aiming at minimizing the makespan. More precisely, we provide a 2-approximation algorithm for identical platforms, a Fully Polynomial Time Approximation Scheme (FPATS) under the assumption of large processor counts and a 2-approximation algorithm for a fixed number of heterogeneous platforms. Most of the proposed algorithms combine a dual approximation scheme with a novel approach to improve the dual approximation algorithm. All results can be extended to the contiguous case, i.e., a task can only be executed by contiguously numbered processors. [ABSTRACT FROM AUTHOR]

An efficient partial ellipsoid approximation scheme is presented to find a 1 ⌈ m 2 ⌉ -approximation solution to the nonconvex homogeneous quadratic optimization with m convex quadratic constraints, where ⌈ x ⌉ is the smallest integer larger than or equal to x. If there is an additional nonconvex quadratic constraint beyond the m convex constraints, we can use the new scheme to find a 1 m -approximation solution. [ABSTRACT FROM AUTHOR]

We consider a class of stochastic online matching problems, where a set of sequentially arriving jobs are to be matched to a group of workers. The objective is to maximize the total expected reward, defined as the sum of the rewards of each matched worker-job pair. Each worker can be matched to multiple jobs subject to the constraint that previously matched jobs are completed. We provide constant approximation algorithms for different variations of this problem with equal-length jobs. [ABSTRACT FROM AUTHOR]

In this study, We aim to design a Dynamic Clustering scheme to maximize the Weighted Sum Rate in Ultra-Dense Cloud Radio Access Network (UD-CRAN) where mm-Wave fronthaul links with limited capacity is deployed. To improve the network performance in terms of users' data rate, The Non-Coherent Joint Transmission is considered which is the superior transmission strategy in the limited fronthaul capacity regime. The Dynamic Clustering is proposed, which has the potential to optimize RRH selection and form a sparse beamforming vector for each user. In this study, we investigate and analyze the closed-form expressions of users' data rate and use the l 1 n o r m to approximate the non-convex fronthaul capacity constraint as a convex weighted power constraint. then, We developed a modified Successive Convex approximation-based algorithm to solve the complicated optimization problem. Our simulation results indicate that in UD-CRAN with mm-Wave fronthaul links, the proposed Dynamic Clustering improve the performance of the system significantly. [ABSTRACT FROM AUTHOR]

We study geometric variations of the discriminating code problem. In the discrete version of the problem, a finite set of points P and a finite set of objects S are given in R d . The objective is to choose a subset S ∗ ⊆ S of minimum cardinality such that for each point p i ∈ P , the subset S i ∗ ⊆ S ∗ covering p i satisfies S i ∗ ≠ ∅ , and each pair p i , p j ∈ P , i ≠ j , we have S i ∗ ≠ S j ∗ . In the continuous version of the problem, the solution set S ∗ can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case ( d = 1 ), the points in P are placed on a horizontal line L, and the objects in S are finite-length line segments aligned with L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in one dimension. Still for the 1-dimensional discrete version, we design a polynomial-time 2-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length. We then study the 2-dimensional case ( d = 2 ) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-complete, and design polynomial-time approximation algorithms that produce (16 · O P T + 1) -approximate and (64 · O P T + 1) -approximate solutions respectively, using rounding of suitably defined integer linear programming problems. Finally, we apply our techniques to a related variant of the discrete problem, where instead of points and geometric objects we just have a set S of objects. The goal is to select a small subset S ∗ of objects so that all objects of S are discriminated by their intersection with the objects of S ∗ . This problem can be viewed as a graph problem by stating it in terms of the vertices of the geometric intersection graph of S. Under this graph-theoretical form, it is known as the identifying code problem. We show that the identifying code problem for axis-parallel unit square intersection graphs (in d = 2 ) can be solved in the same manner as for the discrete version of the discriminating code problem for unit square objects described above, and all our positive approximation results still hold in this setting. [ABSTRACT FROM AUTHOR]

In the Metric Capacitated Covering (MCC) problem, given a set of balls B in a metric space P with metric d and a capacity parameter U, the goal is to find a minimum sized subset B ′ ⊆ B and an assignment of the points in P to the balls in B ′ such that each point is assigned to a ball that contains it and each ball is assigned with at most U points. MCC achieves an O (log | P |) -approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of o (log | P |) even with β < 3 factor expansion of the balls. Bandyapadhyay et al. [Discrete and Computational Geometry 2019] showed that one can obtain an O(1)-approximation for the problem with 6.47 factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound 3 and the upper bound 6.47. In this current work, we show that it is possible to obtain an O(1)-approximation with only 4.24 factor expansion of the balls. Moreover, we show a similar upper bound of 5 for a more generalized version of MCC for which the best previously known bound was 9. We also study a closely related problem where instead of the upper bound, one needs to satisfy a lower bound on the number of points assigned to each ball in the solution. For this problem, we give an exact algorithm with only 5.83 factor expansion of the balls. All of our algorithms are based on LP rounding schemes that heavily exploit structure of fractional optimal solution. [ABSTRACT FROM AUTHOR]

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement– odd , even , or unconstrained –of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparseT-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem. [ABSTRACT FROM AUTHOR]

We consider the intractable problem of finding several edge-disjoint spanning trees of the minimum total weight with a given diameter in complete undirected graph in current paper. The weights of edges of a graph are random variables from several continuous distributions: uniform, biased truncated exponential, biased truncated normal. The approximation algorithm with time complexity (n2), where n is number of vertices in graph, is proposed for solving this problem. The asymptotic optimality conditions for constructed algorithm is presented for each considered probabilistic distribution. [ABSTRACT FROM AUTHOR]