Search

This study analyzes the conditional gradient method for constrained multiobjective optimization problems, also known as the Frank–Wolfe method. We assume that the objectives are continuously differentiable, and the constraint set is convex and compact. We employ an average-type nonmonotone line search, which takes the average of the recent objective function values. The asymptotic convergence properties without convexity assumptions on the objective functions are established. We prove that every limit point of the sequence of iterates that is obtained by the proposed method is a Pareto critical point. An iteration-complexity bound is provided regardless of the convexity assumption on the objective functions. The effectiveness of the suggested approach is demonstrated by applying it to several benchmark test problems. In addition, the efficiency of the proposed algorithm in generating approximations of the entire Pareto front is compared to the existing Hager–Zhang conjugate gradient method, the steepest descent method, the monotone conditional gradient method, and a nonmonotone conditional gradient method. In finding empirical comparison, we utilize two commonly used performance matrices—inverted generational distance and hypervolume indicators. [ABSTRACT FROM AUTHOR]

This paper considers approximation algorithms for generalized k-median problems. These problems can be informally described as k-median with a constant number of extra constraints, and includes k-median with outliers, and knapsack median. Our first contribution is a pseudo-approximation algorithm for generalized k-median that outputs a 6.387-approximate solution, with a constant number of fractional variables. The algorithm builds on the iterative rounding framework introduced by Krishnaswamy, Li, and Sandeep for k-median with outliers as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). The main technical innovation is allowing richer constraint sets in the iterative rounding and using the structure of the resulting extreme points. Using our pseudo-approximation algorithm, we give improved approximation algorithms for k-median with outliers and knapsack median. This involves combining our pseudo-approximation with pre- and post-processing steps to round a constant number of fractional variables at a small increase in cost. Our algorithms achieve approximation ratios 6.994+ϵ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$6.994 + \epsilon $$\end{document} and 6.387+ϵ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$6.387 + \epsilon $$\end{document} for k-median with outliers and knapsack median, respectively. These improve on the best-known approximation ratio 7.081+ϵ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$7.081 + \epsilon $$\end{document} for both problems as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). [ABSTRACT FROM AUTHOR]

Additive coefficient models generalize linear regression models by assuming that the relationship between the response and some covariates is linear, while their regression coefficients are additive functions. Because of its advantages in dealing with the “curse of dimensionality”, additive coefficient models gain a lot of attention. The commonly used estimation methods for additive coefficient models are not robust against high leverage points. To circumvent this difficulty, we develop a robust variable selection procedure based on the exponential squared loss function and group penalty for the additive coefficient models, which can tackle outliers in the response and covariates simultaneously. Under some regularity conditions, we show that the oracle estimator is a local solution of the proposed method. Furthermore, we apply the local linear approximation and minorization-maximization algorithm for the implementation of the proposed estimator. Meanwhile, we propose a data-driven procedure to select the tuning parameters. Simulation studies and an application to a plasma beta-carotene level data set illustrate that the proposed method can offer more reliable results than other existing methods in contamination schemes. [ABSTRACT FROM AUTHOR]

The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times O(n8)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^8)$$\end{document} and O(n4)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^4)$$\end{document} respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in O(n2)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^2)$$\end{document} time, i.e., when two starting points of the two tours are given as input. [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]

Interaction effect across complementary products plays an important role in characterizing the optimal inventory policy. The inventory levels of complementary products are interrelated due to interaction between demand streams. In this paper, we consider a periodic review base-stock policy in the presence of two complementary products with interrelated demands and joint replenishment. Demands are modeled by a Poisson process and any unmet demand is lost. Demands can be in sets of one unit of each or jointly. If an arrival demand requests two products jointly and one of the products is not in stock, then the whole demand is lost. We aim to investigate how this interrelated demand phenomenon influences the optimal base-stock levels and the period length of a periodic review policy. We utilize the renewal reward theorem to derive the explicit expression of the expected profit rate in the system. The goal is to determine the optimal period length and the base-stock levels such that the expected profit rate is maximized. Enumeration and approximation algorithms are employed to find the optimal and near-optimal solutions, respectively. The approximation algorithm is based on a scenario with independent demand processes which results in an explicit expression for the long-run profit per time unit and leads to analytical solutions for optimal policies. Our numerical results reveal that the solutions obtained by the approximation algorithm are close to optimal solutions. Numerical experiences show that the maximum profit in the system is achieved if the proportion of customers with jointly demand increases. Moreover, the interaction effect between demand processes has a significant impact on the control policy performance when the units lost sales and unit holding costs are high, and the demand rare is low. [ABSTRACT FROM AUTHOR]

The aim of this paper is the study of trapezoidal approximation operators, preserving more indicators of fuzzy numbers, relationships between them and their applications. Initial results lead to achieve three main trapezoidal approximation operators that one of them preserves the core, value and the ambiguity, and another one preserves the core and the expected interval, and third operator preserves the value, ambiguity and expected interval. The related concepts and the important properties of these operators and also, comparisons between them are brought, in details. Finally, a ranking method, an approximation operator preserving the most indicators of fuzzy numbers, and a trapezoidal approximation algorithm with its advantages and comparative examples are given as practical applications of the obtained results. [ABSTRACT FROM AUTHOR]

Computing shortest paths from a single source is one of the central problems studied in the CONGEST model of distributed computing. After many years in which no algorithmic progress was made, Elkin [STOC '17] provided the first improvement over the distributed Bellman-Ford algorithm. Since then, several improved algorithms have been published. The state-of-the-art algorithm for weighted directed graphs (with polynomially bounded non-negative integer weights) requires O ~ (min { n D 1 / 2 , n D 1 / 4 + n 3 / 5 + D }) rounds [Forster and Nanongkai, FOCS '18], which is still quite far from the known lower bound of Ω ~ (n + D) rounds [Elkin, STOC '04]; here D is the diameter of the underlying network and n is the number of vertices in it. For the (1 + o (1)) -approximate version of this problem and the same class of graphs, Forster and Nanongkai [FOCS '18] obtained a better upper bound of O ~ (n D 1 / 4 + D) rounds. In the same paper, they stated that achieving the same bound for the exact case remains a major open problem. In this paper we resolve the above mentioned problem by devising a new randomized algorithm for computing shortest paths from a single source in O ~ (n D 1 / 4 + D) rounds. Our algorithm is based on a novel weight-modifying technique that allows us to compute approximate distances that preserve a certain form of the triangle inequality for the edges in the graph. [ABSTRACT FROM AUTHOR]

We propose an algorithm to generate inner and outer polyhedral approximations to the upper image of a bounded convex vector optimization problem. It is an outer approximation algorithm and is based on solving norm-minimizing scalarizations. Unlike Pascoletti–Serafini scalarization used in the literature for similar purposes, it does not involve a direction parameter. Therefore, the algorithm is free of direction-biasedness. We also propose a modification of the algorithm by introducing a suitable compact subset of the upper image, which helps in proving for the first time the finiteness of an algorithm for convex vector optimization. The computational performance of the algorithms is illustrated using some of the benchmark test problems, which shows promising results in comparison to a similar algorithm that is based on Pascoletti–Serafini scalarization. [ABSTRACT FROM AUTHOR]

A weak conical greedy algorithm is introduced with respect to an arbitrary positive complete dictionary in a Hilbert space; this algorithm gives an approximation of an arbitrary space element by a combination of dictionary elements with nonnegative coefficients. The convergence of this algorithm is proved and an estimate of the convergence rate for the elements of the convex hull of the dictionary is given. [ABSTRACT FROM AUTHOR]

Partial differential equations (PDEs) are a fundamental tool in the modeling of many real-world phenomena. In a number of such real-world phenomena the PDEs under consideration contain gradient-dependent nonlinearities and are high-dimensional. Such high-dimensional nonlinear PDEs can in nearly all cases not be solved explicitly, and it is one of the most challenging tasks in applied mathematics to solve high-dimensional nonlinear PDEs approximately. It is especially very challenging to design approximation algorithms for nonlinear PDEs for which one can rigorously prove that they do overcome the so-called curse of dimensionality in the sense that the number of computational operations of the approximation algorithm needed to achieve an approximation precision of size ε > 0 grows at most polynomially in both the PDE dimension d ∈ N and the reciprocal of the prescribed approximation accuracy ε . In particular, to the best of our knowledge there exists no approximation algorithm in the scientific literature which has been proven to overcome the curse of dimensionality in the case of a class of nonlinear PDEs with general time horizons and gradient-dependent nonlinearities. It is the key contribution of this article to overcome this difficulty. More specifically, it is the key contribution of this article (i) to propose a new full-history recursive multilevel Picard approximation algorithm for high-dimensional nonlinear heat equations with general time horizons and gradient-dependent nonlinearities and (ii) to rigorously prove that this full-history recursive multilevel Picard approximation algorithm does indeed overcome the curse of dimensionality in the case of such nonlinear heat equations with gradient-dependent nonlinearities. [ABSTRACT FROM AUTHOR]

In multistage perfect matching problems, we are given a sequence of graphs on the same vertex set and are asked to find a sequence of perfect matchings, corresponding to the sequence of graphs, such that consecutive matchings are as similar as possible. More precisely, we aim to maximize the intersections, or minimize the unions between consecutive matchings. We show that these problems are NP-hard even in very restricted scenarios. As our main contribution, we present the first non-trivial approximation algorithms for these problems: On the one hand, we devise a tight approximation on graph sequences of length two (2-stage graphs). On the other hand, we propose several general methods to deduce multistage approximations from blackbox approximations on 2-stage graphs. [ABSTRACT FROM AUTHOR]

It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most k vertices whose deletion results in a chordal graph when parameterized by k. While this investigation fits naturally into the recent trend of what is called 'structural parameterizations', here we assume that the deletion set is not given. One method to solve them is to compute a k-sized or an approximate (f(k) sized, for a function f) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least k O (k) n O (1) running time when we use the known parameterized or approximation algorithms for finding a k-sized chordal deletion set on an n vertex graph. In this work, we design 2 O (k) n O (1) time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in 2 O (k) n O (1) time where each bag is a union of four cliques and O (k) vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. Our algorithms are, what are sometimes called permissive in the sense that given an integer k, they detect whether the graph has no chordal vertex deletion set of size at most k or output the special tree decomposition and solve the problem. We also show lower bounds for the problems we deal with under the strong exponential time hypothesis. [ABSTRACT FROM AUTHOR]

The minimum hitting set of bundles problem (Mhsb) is a natural generalization of the minimum hitting set problem, where instead of hitting single elements, bundles of elements are hit. More specifically, we are given a ground set of elements and a family of sets. Every set in this family contains bundles of elements, which are subsets of the ground set. The task is to find a collection of elements of minimum size such that at least one bundle of every set in the family is hit. Motivated by several applications, we consider Mhsb restricted to interval and 2-dimensional interval bundles. We study the computational complexity and give polynomial-time algorithms for several classes of instances with these special structured bundles. [ABSTRACT FROM AUTHOR]

The relationship between structure and corrosion inhibition of a series of twenty-eight quinoline and pyridine derivatives has been established through the investigation of quantum descriptors calculated with PBE/6–311 + + G** method. A quantitative structure–property relationship (QSPR) model was obtained by examining these descriptors using a genetic algorithm approximation method based on a multiple linear regression analysis. The results indicate that the efficiency of corrosion inhibitors is strongly associated with hardness (η), minimal electrostatic potential (ESPmin), and volume (V) descriptors. Furthermore, the validity of the proposed model is corroborated by an adsorption study on an iron surface Fe(110). [ABSTRACT FROM AUTHOR]

This work addresses the problem of traffic splitting for improving the overall delay jitter performance in the uplink multi-access system. We propose a packet-scheduling paradigm based on stochastic approximation algorithm to distribute the source traffic across the multiple network paths/interfaces. We first provide an analytical model and the delay jitter analysis for an individual interface. Later we formulate the traffic splitting problem as an optimization problem to learn the optimal split across the interfaces. We share the experimental results for the video and constant bit rate traffic on real networks (Wi-Fi or cellular networks) and convergence of our system using the proposed scheme in the dynamic network environment. The paradigm proposed in the paper is general and can be adapted to different objective functions. [ABSTRACT FROM AUTHOR]

A class of binary sequences with period 2p is constructed using generalized cyclotomic classes, and their linear complexity, minimal polynomial over F q as well as 2-adic complexity are determined using Gauss period and group ring theory. The results show that the linear complexity of these sequences attains the maximum when p ≡ ± 1 (mod 8) and is equal to p+1 when p ≡ ± 3 (mod 8) over extension field. Moreover, the 2-adic complexity of these sequences is maximum. According to Berlekamp–Massey(B–M) algorithm and the rational approximation algorithm (RAA), these sequences have quite good cryptographic properties in the aspect of linear complexity and 2-adic complexity. [ABSTRACT FROM AUTHOR]

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]

Fuzzy Knowledge Graph (FKG) has recently been emerging as one of the key techniques for supporting classification and decision-making problems. FKG is a novel concept that was firstly introduced in 2020 by integrating approximate reasoning with inference mechanism to find labels of new records, which are impossible for inference by the rule base. However, one of the key limitations of FKG is the use of a single pair to find new records' label that leads to low performance in approximation. This paper presents a novel approach of using FKG pairs instead of a single pair as in the classical model. A novel FKG-Pairs model including a new representing method and an approximation algorithm is presented. Theoretical analysis of the FKG-Pairs model such as identification of a threshold for the best value (k∗) pairs is also investigated. Finally, to validate the proposed model, a numerical example and the experiments on the UCI datasets are presented. In addition, a two-way ANOVA method is also conducted to validate the model statistically. The novel concept about the FKG-Pairs given in this paper exposes new ideas in the effort to realize the much-anticipated decision-making and classification problems in fuzzy systems [ABSTRACT FROM AUTHOR]

Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA's performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified. [ABSTRACT FROM AUTHOR]

The manufacturing industry has been seeking to design an energy-efficient assembly system. Reasonable assembly line balancing (ALB) can reduce the energy consumption of the assembly production subsystem. Meanwhile, appropriate part feeding (PF) can reduce the energy consumption of the assembly distribution subsystem. However, existing research considers energy efficiency-related issues by treating ALB and PF separately, which misses the potential opportunity for energy savings for the entire assembly system. Given that ALB and PF are closely interrelated, this study investigates the energy-efficient integration of assembly line balancing and part feeding (EIALBPF) problems by a modified genetic algorithm (MGA). First, a mathematical model of the EIALBPF problem is established to simultaneously minimize the number of stations, the number of supermarkets, and total energy consumption. Moreover, to solve the EIALBPF problem effectively, a modified genetic algorithm is designed with mixed encoding and repair strategy. Finally, a series of computational experiments are conducted. The results demonstrate that (i) the proposed method significantly reduces the total energy consumption of the entire assembly system compared with the traditional separate programming method and (ii) the proposed MGA outperforms the nested genetic algorithm in terms of the approximation to the true frontier and computational efficiency. As such, this study may be a valuable supplement to existing efforts aiming at developing energy-efficient manufacturing techniques. [ABSTRACT FROM AUTHOR]

For a family of graphs F , Weighted F -Deletion is the problem for which the input is a vertex weighted graph G = (V , E) and the goal is to delete S ⊆ V with minimum weight such that G \ S ∈ F . Designing a constant-factor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3-leaf power graphs, and interval graphs are known to admit constant-factor approximation algorithms, but the question is open for chordal graphs and distance-hereditary graphs. In this paper, we add one more class to this list by presenting a constant-factor approximation algorithm when F is the intersection of chordal graphs and distance-hereditary graphs. They are known as ptolemaic graphs and form a superset of both block graphs and 3-leaf power graphs above. Our proof presents new properties and algorithmic results on inter-clique digraphs as well as an approximation algorithm for a variant of Feedback Vertex Set that exploits this relationship (named Feedback Vertex Set with Precedence Constraints), each of which may be of independent interest. [ABSTRACT FROM AUTHOR]

Given a set of players P, a set of indivisible resources R, and a set of non-negative values { v pr } p ∈ P , r ∈ R , an allocation is a partition of R into disjoint subsets { C p } p ∈ P so that each player p is assigned the resources in C p . The max-min fair allocation problem is to determine the allocation that maximizes min p ∑ r ∈ C p v pr . In the restricted case of this problem, each resource r has an intrinsic value v r , and v pr = v r for every player p who desires r and v pr = 0 for every player p who does not. We study the restricted max-min fair allocation problem in this paper. For this problem, the configuration LP has played an important role in estimating and approximating the optimal solution. Our first result is an upper bound of 3 21 26 on the integrality gap, which is currently the best. It is obtained by a tighter analysis of the local search of Asadpour et al. [TALG'12]. It remains unknown whether this local search runs in polynomial time or not. Our second result is a polynomial-time algorithm that achieves an approximation ratio of 4 + δ for any constant δ ∈ (0 , 1) . Our algorithm can be seen as a generalization of the aforementioned local search. [ABSTRACT FROM AUTHOR]

For some β ≥ 1 / 2 , a Δ β -metric graph G = (V , E , w) is a complete edge-weighted graph such that w (v , v) = 0 , w (u , v) = w (v , u) , and w (u , v) ≤ β · (w (u , x) + w (x , v)) for all vertices u , v , x ∈ V . A graph H = (V ′ , E ′) is called a spanning subgraph of G = (V , E) if V ′ = V and E ′ ⊆ E . Given a positive integer p, let H be a spanning subgraph of G satisfying the three conditions: (i) there exists a vertex subset C ⊆ V such that C forms a clique of size p in H; (ii) the set V \ C forms an independent set in H; and (iii) each vertex v ∈ V \ C is adjacent to exactly one vertex in C. The vertices in C are called hubs and the vertices in V \ C are called non-hubs. The Δ β - p -Hub Center Problem ( Δ β - p HCP) is to find a spanning subgraph H of G satisfying all the three conditions such that the diameter of H is minimized. In this paper, we study Δ β - p HCP for all β ≥ 1 2 . We show that for any ϵ > 0 , to approximate Δ β - p HCP to a ratio g (β) - ϵ is NP-hard and we give r (β) -approximation algorithms for the same problem where g (β) and r (β) are functions of β . For 3 - 3 2 < β ≤ 5 + 5 10 , we give an approximation algorithm that reaches the lower bound of approximation ratio g (β) where g (β) = 3 β - 2 β 2 3 (1 - β) if 3 - 3 2 < β ≤ 2 3 and g (β) = β + β 2 if 2 3 ≤ β ≤ 5 + 5 10 . For 5 + 5 10 ≤ β ≤ 1 , we show that g (β) = 4 β 2 + 3 β - 1 5 β - 1 and r (β) = min { β + β 2 , 4 β 2 + 5 β + 1 5 β + 1 } . Additionally, for β ≥ 1 , we show that g (β) = β · 4 β - 1 3 β - 1 and r (β) = min { β 2 + 4 β 3 , 2 β } . For β ≥ 2 , the upper bound on the approximation ratio r (β) = 2 β is linear in β . For 3 - 3 2 < β ≤ 5 + 5 10 , we give an approximation algorithm that reaches the lower bound of approximation ratio g (β) where g (β) = 3 β - 2 β 2 3 (1 - β) if 3 - 3 2 < β ≤ 2 3 and g (β) = β + β 2 if 2 3 ≤ β ≤ 5 + 5 10 . For β ≤ 3 - 3 2 , we show that g (β) = r (β) = 1 , i.e., Δ β - p HCP is polynomial-time solvable. [ABSTRACT FROM AUTHOR]

We consider a problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Because a distributive lattice is used to represent a dependency constraint, the problem can represent a dependency constrained version of a submodular maximization problem on a set. We propose a ( 1 - 1 / e )-approximation algorithm for this problem. To achieve this result, we generalize the continuous greedy algorithm to distributive lattices: We choose a median complex as a continuous relaxation of the distributive lattice and define the multilinear extension on it. We show that the median complex admits special curves, named uniform linear motions. The multilinear extension of a DR-submodular function is concave along a positive uniform linear motion, which is a key property used in the continuous greedy algorithm. [ABSTRACT FROM AUTHOR]

A displacement aggregation strategy is proposed for the curvature pairs stored in a limited-memory BFGS (a.k.a. L-BFGS) method such that the resulting (inverse) Hessian approximations are equal to those that would be derived from a full-memory BFGS method. This means that, if a sufficiently large number of pairs are stored, then an optimization algorithm employing the limited-memory method can achieve the same theoretical convergence properties as when full-memory (inverse) Hessian approximations are stored and employed, such as a local superlinear rate of convergence under assumptions that are common for attaining such guarantees. To the best of our knowledge, this is the first work in which a local superlinear convergence rate guarantee is offered by a quasi-Newton scheme that does not either store all curvature pairs throughout the entire run of the optimization algorithm or store an explicit (inverse) Hessian approximation. Numerical results are presented to show that displacement aggregation within an adaptive L-BFGS scheme can lead to better performance than standard L-BFGS. [ABSTRACT FROM AUTHOR]

We are given a set of parallel jobs that have to be executed on a set of speed-scalable processors varying their speeds dynamically. Running a job at a slower speed is more energy-efficient, however, it takes a longer time and affects the performance. Every job is characterized by the processing volume and the number or the set of the required processors. Our objective is to minimize the maximum completion time so that the energy consumption is not greater than a given energy budget. For various particular cases, we propose polynomial-time approximation algorithms, consisting of two stages. At the first stage, we give an auxiliary convex program. By solving this problem, we get processing times of jobs and a lower bound on the makespan. Then, at the second stage, we transform our problem into the corresponding scheduling problem with the constant speed of processors and construct a feasible schedule. We also obtain an "almost exact" solution for the preemptive settings based on a configuration linear program. [ABSTRACT FROM AUTHOR]

Energy harvesting technologies allow wireless devices to be recharged by the surrounding environment, providing wireless sensor networks (WSNs) with higher performance and longer lifetime. However, directly building a wireless sensor network with energy harvesting nodes is very costly. A compromise is upgrading existing networks with energy harvesting technologies. In this paper, we focus on prolonging the lifetime of WSNs with the help of energy harvesting relays (EHRs). EHRs are responsible for forwarding data for sensor nodes, allowing them to become terminals and thus extending their lifetime. We aim to deploy a minimum number of relays covering the whole network. As EHRs have several special properties such as the energy harvesting and depletion rate, it brings great research challenges to seek an optimal deployment strategy. To this end, we propose an approximation algorithm named Effective Relay Deployment Algorithm, which can be divided into two phases: disk covering and connector insertion using the partitioning technique and the Steinerization technique, respectively. Based on probabilistic analysis, we further optimize the performance ratio of our algorithm to (5 + 6/K) where K is an integer denoting the side length of a cell after partitioning. Our extensive simulation results show that our algorithm can reduce the number of EHRs to be deployed by up to 45% compared with previous work and thus validate the efficiency and effectiveness of our solution. [ABSTRACT FROM AUTHOR]

In this work, we consider optimal stopping problems with model uncertainty incorporated into the formulation of the underlying objective function. Typically, the robust, efficient hedging of American options in incomplete markets may be described as optimal stopping of such kind. Based on a generalisation of the additive dual representation of Rogers (Math. Financ. 12:271–286, 2002) to the case of optimal stopping under model uncertainty, we develop a novel regression-based Monte Carlo algorithm for the approximation of the corresponding value function. The algorithm involves optimising a penalised empirical dual objective functional over a class of martingales. This formulation allows us to construct upper bounds for the optimal value with reduced complexity. Finally, we carry out a convergence analysis of the proposed algorithm and illustrate its performance by several numerical examples. [ABSTRACT FROM AUTHOR]

A subset S of nodes in a graph G is a k-connected m-dominating set ((k, m)-cds) if the subgraph G[S] induced by S is k-connected and every v ∈ V \ S has at least m neighbors in S. In the k-Connectedm-Dominating Set ((k, m)-CDS) problem, the goal is to find a minimum weight (k, m)-cds in a node-weighted graph. For m ≥ k we obtain the following approximation ratios. For unit disk graphs we improve the ratio O (k ln k) of Nutov (Inf Process Lett 140:30–33, 2018) to min m 2 (m - k + 1) 2 , k 2 / 3 · O (ln 2 k) —this is the first sublinear ratio for the problem, and the first polylogarithmic ratio O (ln 2 k) / ϵ 2 when m ≥ (1 + ϵ) k ; furthermore, we obtain ratio min m m - k + 1 , k · O (ln 2 k) for uniform weights. For general graphs our ratio O (k ln n) improves the previous best ratio O (k 2 ln n) of Nutov (2018) and matches the best known ratio for unit weights of Zhang et al. (INFORMS J Comput 30(2):217–224, 2018). These results are obtained by showing the same ratios for the Subsetk-Connectivity problem when the set of terminals is an m-dominating set. [ABSTRACT FROM AUTHOR]

The paper introduces a new weak approximation algorithm for stochastic differential equations (SDEs) of McKean–Vlasov type. The arbitrary order discretization scheme is available and is given using Malliavin weights, certain polynomial weights of Brownian motion, which play a role as correction of the approximation. The new weak approximation scheme works even if the test function is not smooth. In other words, the expectation of irregular functionals of McKean–Vlasov SDEs such as probability distribution functions are approximated through the proposed scheme. The effectiveness of the higher order scheme is confirmed by numerical examples for McKean–Vlasov SDEs including the Kuramoto model. [ABSTRACT FROM AUTHOR]

Impartial selection has recently received much attention within the multi-agent systems community. The task is, given a directed graph representing nominations to the members of a community by other members, to select a member with the highest number of nominations. This seemingly trivial goal becomes challenging when there is an additional impartiality constraint, requiring that no single member can influence her chance of being selected. Recent progress has identified impartial selection rules with optimal approximation ratios. Moreover, it was noted that worst-case instances are graphs with few vertices. Motivated by this fact, we propose the study of additive approximation, the difference between the highest number of nominations and the number of nominations of the selected member, as an alternative measure of the quality of impartial selection. Our positive results include two randomized impartial selection mechanisms which have additive approximation guarantees of Θ (n) and Θ (n 2 / 3 ln 1 / 3 n) for the two most studied models in the literature, where n denotes the community size. We complement our positive results by providing negative results for various cases. First, we provide a characterization for the interesting class of strong sample mechanisms, which allows us to obtain lower bounds of n − 2, and of Ω (n) for their deterministic and randomized variants respectively. Finally, we present a general lower bound of 3 for all deterministic impartial mechanisms. [ABSTRACT FROM AUTHOR]

We study the problem of finding maximum weakly stable matchings when preference lists are incomplete and contain one-sided ties of bounded length. We show that if the tie length is at most L, then it is possible to achieve an approximation ratio of 1 + (1 − 1 L) L . We also show that the same ratio is an upper bound on the integrality gap, which matches the known lower bound. In the case where the tie length is at most 2, our result implies an approximation ratio and integrality gap of 5 4 , which matches the known UG-hardness result. [ABSTRACT FROM AUTHOR]

For a continuous multi-objective optimization problem, it is usually not a practical approach to compute all its nondominated points because there are infinitely many of them. For this reason, a typical approach is to compute an approximation of the nondominated set. A common technique for this approach is to generate a polyhedron which contains the nondominated set. However, often these approximations are used for further evaluations. For those applications a polyhedron is a structure that is not easy to handle. In this paper, we introduce an approximation with a simpler structure respecting the natural ordering. In particular, we compute a box-coverage of the nondominated set. To do so, we use an approach that, in general, allows us to update not only one but several boxes whenever a new nondominated point is found. The algorithm is guaranteed to stop with a finite number of boxes, each being sufficiently thin. [ABSTRACT FROM AUTHOR]

Low-rank matrix recovery from an observation data matrix has received considerable attention in recent years, which has a wide range of applications in pattern recognition and computer vision, such as face denoising, background/foreground separation, gait recognition, image alignment, etc. However, existing algorithms suffer from the interference of small noise, for example, low-level Gaussian noise, which makes their performance not satisfactory. To address this issue, we are based on the unconstrained nonconvex relaxed minimization model for low-rank and sparse matrices recovery using low-rank matrix decomposition, and propose a novel efficient and effective solving algorithm in terms of direction matrices and step sizes alternating iteration in this paper. The three direction matrices are deduced using Newton method, Taylor expansion and so forth, and the appropriate step size of the direction sparse matrix is searched by the nonmonotonous step size linear search technique efficiently. In theory, we provide the convergence theorem of the proposed algorithm. Experimentally, its efficiency and effectiveness are illustrated under appropriate conditions. [ABSTRACT FROM AUTHOR]

Metric data plays an important role in various settings, for example, in metric-based indexing, clustering, classification, and approximation algorithms in general. Due to measurement error, noise, or an inability to completely gather all the data, a collection of distances may not satisfy the basic metric requirements, most notably the triangle inequality. In this paper we initiate the study of the metric violation distance problem: given a set of pairwise distances, modify the minimum number of distances such that the resulting set forms a metric. Three variants of the problem are considered, based on whether distances are allowed to only decrease, only increase, or the general case which allows both decreases and increases. We show that while the decrease only variant is polynomial time solvable, the increase only and general variants are NP-Complete, and moreover cannot in polynomial time be approximated to any ratio better than the minimum vertex cover problem. We then provide approximation algorithms for the increase only and general variants of the problem, by proving interesting necessary and sufficient conditions on the optimal solution, which are used to approximately reduce to a purely combinatorial problem for which we provide matching asymptotic upper and lower bounds. [ABSTRACT FROM AUTHOR]

Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph G = (V , E) with edge costs c ∈ R ≥ 0 E , a root r ∈ V and k terminals K ⊆ V , we need to output the minimum-cost arborescence in G that contains an r → t path for every t ∈ K . Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time O (log 2 k / log log k) -approximation Algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general Degree-Bounded Directed Steiner Tree (DB-DST) problem, where we are additionally given a degree bound d v on each vertex v ∈ V , and we require that every vertex v in the output tree has at most d v children. We give a quasi-polynomial time (O (log n log k) , O (log 2 n)) -bicriteria approximation: The Algorithm produces a solution with cost at most O (log n log k) times the cost of the optimum solution that violates the degree constraints by at most a factor of O (log 2 n) . This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of O (log 2 n) is an O (log n) -factor away from the approximation lower bound of Ω (log n) from the set-cover hardness. The hardness result holds even on the special case of the Degree-Bounded Group Steiner Tree problem on trees (DB-GST-T). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an (O (log n log k) , O (log n)) -bicriteria approximation Algorithm for DB-GST-T. [ABSTRACT FROM AUTHOR]

The problem of approximation by low-rank matrices is found everywhere in computational mathematics. Traditionally, this problem is solved in the spectral or Frobenius norm, where the approximation efficiency is associated with the rate of decrease of the matrix singular values. However, recent results show that this requirement is not necessary in other norms. In this paper, a method for solving the problem of approximating by low-rank matrices in Chebyshev's norm is proposed. It makes it possible to construct effective approximations of matrices for which singular values do not decrease in an acceptable amount time. [ABSTRACT FROM AUTHOR]

Submodular maximization has been the backbone of many important machine-learning problems, and has applications to viral marketing, diversification, sensor placement, and more. However, the study of maximizing submodular functions has mainly been restricted in the context of selecting a set of items. On the other hand, many real-world applications require a solution that is a ranking over a set of items. The problem of ranking in the context of submodular function maximization has been considered before, but to a much lesser extent than item-selection formulations. In this paper, we explore a novel formulation for ranking items with submodular valuations and budget constraints. We refer to this problem as max-submodular ranking (MSR ). In more detail, given a set of items and a set of non-decreasing submodular functions, where each function is associated with a budget, we aim to find a ranking of the set of items that maximizes the sum of values achieved by all functions under the budget constraints. For the MSR problem with cardinality- and knapsack-type budget constraints we propose practical algorithms with approximation guarantees. In addition, we perform an empirical evaluation, which demonstrates the superior performance of the proposed algorithms against strong baselines. [ABSTRACT FROM AUTHOR]

This paper explores the design and hardware efficient realization of low complexity filter bank-based reconfigurable channelizers suitable for wireless receivers. The reconfigurability is achieved by deriving a set of non-uniform filter banks with different sampling factor combinations from a low complexity partial cosine modulated uniform filter bank, by combining different number of its neighbouring channels. The hardware complexity comparison of the filter bank channelizer designed by the proposed approach, with the existing works proves that this approach requires less number of multipliers in its realization to extract the same set of communication standards. To reduce the power and complexity of the multipliers needed for the hardware realization of the filter coefficients, an approximation algorithm, which increases the zeros in the binary represented filter coefficients is employed. The synthesis results show that the algorithm offers a considerable reduction in the hardware and power consumptions of the filter bank. [ABSTRACT FROM AUTHOR]

The piecewise monotonic approximation problem makes the least changes to n univariate noisy data so that the piecewise linear interpolant to the new values is composed of at most k monotonic sections. The term "least changes" is defined in the sense of a global sum of strictly convex functions of changes. The main difficulty in this calculation is that the extrema of the interpolant have to be found automatically, but the number of all possible combinations of extrema can be O (n k - 1) , which makes not practicable to test each one separately. It is known that the case k = 1 is straightforward, and that the case k > 1 reduces to partitioning the data into at most k disjoint sets of adjacent data and solving a k = 1 problem for each set. Some ordering relations of the extrema are studied that establish three quite efficient algorithms by using a binary search method for partitioning the data. In the least squares case the total work is only O (n σ + k σ log 2 σ) computer operations when k ≥ 3 and is only O (n) when k = 1 or 2, where σ - 2 is the number of sign changes in the sequence of the first differences of the data. Fortran software has been written for this case and the numerical results indicate superior performance to existing algorithms. Some examples with real data illustrate the method. Many applications of the method arise from bioinformatics, energy, geophysics, medical imaging, and peak finding in spectroscopy, for instance. [ABSTRACT FROM AUTHOR]

In the problem of maximizing regularized two-stage submodular functions in streams, we assemble a family ℱ of m functions each of which is submodular and is visited in a streaming style that an element is visited for only once. The aim is to choose a subset S of size at most ℓ from the element stream V , so as to maximize the average maximum value of these functions restricted on S with a regularized modular term. The problem can be formally casted as max S ⊆ V , | S | ⩽ ℓ 1 m ∑ i = 1 m max T ⊆ S , | T | ⩽ k [ f i (T) − c (T) ] , where c : V → ℝ + is a non-negative modular function and f i : 2 V → ℝ + , ∀ i ∈ { 1 , … , m } is a non-negative monotone non-decreasing submodular function. The well-studied regularized problem of max S ⊆ V , | S | ⩽ k f (S) − c (S) is exactly a special case of the above regularized two-stage submodular maximization by setting m = 1 and ℓ = k. Although f(·) − c(·) is submodular, it is potentially negative and non-monotone and admits no constant multiplicative factor approximation. Therefore, we adopt a slightly weaker notion of approximation which constructs S such that f(S) − c(S) ⩾ ρ · f(O) − c(O) holds against optimum solution O for some ρ ∈ (0, 1). Eventually, we devise a streaming algorithm by employing the distorted threshold technique, achieving a weaker approximation ratio with ρ = 0.2996 for the discussed regularized two-stage model. [ABSTRACT FROM AUTHOR]

Quantum state tomography is a process for estimating an unknown quantum state; which is innately probabilistic. The exponential growth of unknown parameters to be estimated is a fundamental difficulty in realizing quantum state tomography for higher dimensions. Iterative optimization algorithms like self-guided quantum tomography have been effective in robust and accurate ascertaining a quantum state even with exponential growth in Hilbert space. We propose a faster convergent simultaneous perturbation stochastic approximation algorithm which is more practical in a resource-deprived situation for determining the underlying quantum states by incorporating the Barzilai–Borwein two-point step size gradient method with minimal loss of accuracy. [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]

Energy harvesting and source coding are two key techniques that can be exploited to mitigate the device battery limitation in Internet of things (IoT). However, these mitigating techniques come with the expense of adding to the complexity of control and optimization in the digital communication chain. In this paper, to strike a balance between the opposing goals of energy-efficient communication, high-fidelity reconstruction at the IoT gateway, low packet drop ratio, and timeliness of data, we address the delay-constrained joint lossy compression and transmission control problem for an IoT device with rechargeable energy storage. Given the stochastic dynamics emanated from the random nature of the energy harvesting process as well as the fading channel, we formulate a stochastic optimization problem using the formalism of constrained Markov decision process (CMDP) and utilize the standard Lagrangian technique to recast the problem in the unconstrained form. To compute the optimal control policy, we propose a two-timescale stochastic approximation algorithm consisting of some reinforcement learning (RL) algorithms for estimating the CMDP's value function and stochastic gradient descent for estimating the Lagrange multiplier. Specifically, we propose three RL procedures: one based on standard Q-learning, and two accelerated learning procedures, namely post-decision state (PDS) and virtual experience (VE) learning. These algorithms exploit the known system dynamics and batch updates to overcome the slowness caused by the asynchronous updating pattern in Q-learning. Simulation results demonstrate that the proposed PDS and VE learning algorithms speed up the convergence to the optimal control policy by one and two orders of magnitude, respectively. [ABSTRACT FROM AUTHOR]

In recent years, several compressed indexes based on variants of the Burrows–Wheeler transform have been introduced. Some of these are used to index structures far more complex than a single string, as was originally done with the FM-index (Ferragina and Manzini in J. ACM 52(4):552–581, https://doi.org/10.1145/1082036.1082039, 2005). As such, there has been an increasing effort to better understand under which conditions such an indexing scheme is possible. This has led to the introduction of Wheeler graphs (Gagie et al. in Theor Comput Sci 698:67–78, https://doi.org/10.1016/j.tcs.2017.06.016, 2017). Gagie et al. showed that de Bruijn graphs, generalized compressed suffix arrays, and several other BWT related structures can be represented as Wheeler graphs, and that Wheeler graphs can be indexed in a space-efficient way. Hence, being able to recognize whether a given graph is a Wheeler graph, or being able to approximate a given graph by a Wheeler graph, could have numerous applications in indexing. Here we resolve the open question of whether there exists an efficient algorithm for recognizing if a given graph is a Wheeler graph. We show: The problem of recognizing whether a given graph G = (V , E) is a Wheeler graph is NP-complete for any edge label alphabet of size σ ≥ 2 , even when G is a DAG. This holds even on a restricted subset of graphs called d-NFAs for d ≥ 5 . This is in contrast to recent results demonstrating the problem can be solved in polynomial time for d-NFAs where d ≤ 2 . We also show that the recognition problem can be solved in linear time for σ = 1 on graphs without self-loops; There exists an 2 e log σ + O (n + e) time exact algorithm where n = | V | and e = | E | . This algorithm relies on graph isomorphism being computable in strictly sub-exponential time; We define an optimization variant of the problem called Wheeler Graph Violation, abbreviated WGV, where the aim is to identify the smallest set of edges that have to be removed from a graph to obtain a Wheeler graph. We show WGV is APX-hard, even when G is a DAG, implying there exists a constant C > 1 for which there is no C-approximation algorithm (unless P = NP). Also, conditioned on the Unique Games Conjecture, for all C > 1 , it is NP-hard to find a C-approximation, implying WGV is not in APX; We define the Wheeler Subgraph problem, abbreviated WS, where the aim is to find the largest subgraph which is a Wheeler Graph (the dual of WGV). In contrast to WGV, we give an O (σ) -approximation algorithm for the WS problem, implying it is in APX for σ = O (1) . The above findings suggest that most problems under this theme are computationally difficult. However, we identify a class of graphs for which the recognition problem is polynomial-time solvable, raising the question of which properties determine this problem's difficulty. [ABSTRACT FROM AUTHOR]

We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of n tasks and m resources, where each task j uses some subset of the resources. Tasks have random sizes X j , and our goal is to non-adaptively select t tasks to minimize the expected maximum load over all resources, where the load on any resource i is the total size of all selected tasks that use i. For example, when resources are points and tasks are intervals in a line, we obtain an O (log log m) -approximation algorithm. Our technique is also applicable to other problems with some geometric structure in the relation between tasks and resources; e.g., packing paths, rectangles, and "fat" objects. Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show that this LP has an Ω (log ∗ m) integrality gap, even for the problem of selecting intervals on a line; here log ∗ m is the iterated logarithm function. [ABSTRACT FROM AUTHOR]

In the classic maximum coverage problem, we are given subsets T 1 , ... , T m of a universe [n] along with an integer k and the objective is to find a subset S ⊆ [ m ] of size k that maximizes C (S) : = | ∪ i ∈ S T i | . It is well-known that the greedy algorithm for this problem achieves an approximation ratio of (1 - e - 1) and there is a matching inapproximability result. We note that in the maximum coverage problem if an element e ∈ [ n ] is covered by several sets, it is still counted only once. By contrast, if we change the problem and count each element e as many times as it is covered, then we obtain a linear objective function, C (∞) (S) = ∑ i ∈ S | T i | , which can be easily maximized under a cardinality constraint. We study the maximum ℓ -multi-coverage problem which naturally interpolates between these two extremes. In this problem, an element can be counted up to ℓ times but no more; hence, we consider maximizing the function C (ℓ) (S) = ∑ e ∈ [ n ] min { ℓ , | { i ∈ S : e ∈ T i } | } , subject to the constraint | S | ≤ k . Note that the case of ℓ = 1 corresponds to the standard maximum coverage setting and ℓ = ∞ gives us a linear objective. We develop an efficient approximation algorithm that achieves an approximation ratio of 1 - ℓ ℓ e - ℓ ℓ ! for the ℓ -multi-coverage problem. In particular, when ℓ = 2 , this factor is 1 - 2 e - 2 ≈ 0.73 and as ℓ grows the approximation ratio behaves as 1 - 1 2 π ℓ . We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture. This problem is motivated by the question of finding a code that optimizes the list-decoding success probability for a given noisy channel. We show how the multi-coverage problem can be relevant in other contexts, such as combinatorial auctions. [ABSTRACT FROM AUTHOR]

We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are APX -hard to approximate and present constant-factor approximation algorithms based upon two different algorithmic techniques: a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation, and a greedy strategy. We further show that a combination of these techniques can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of these algorithms for problem instances arising in the context of real-world gas transport networks. [ABSTRACT FROM AUTHOR]

An instance of colorfulk-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius ρ such that there exist balls of radius ρ around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations. Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical k-center problem which this problem generalizes. algorithms either opened more than k centers or only worked in the special case when the input points are in the plane. [ABSTRACT FROM AUTHOR]