In this paper, we explore two robust models for the k-median and k-means problems: the outlier-version (k-MedO/k-MeaO) and the penalty-version (k-MedP/k-MeaP), enabling the marking and elimination of certain points as...
详细信息
ISBN:
(数字)9789819723409
ISBN:
(纸本)9789819723393;9789819723409
In this paper, we explore two robust models for the k-median and k-means problems: the outlier-version (k-MedO/k-MeaO) and the penalty-version (k-MedP/k-MeaP), enabling the marking and elimination of certain points as outliers. In k-MedO/k-MeaO, the count of outliers is restricted by a specified integer, while in k-MedP/k-MeaP, there's no explicit limit on outlier quantity, yet each outlier incurs a penalty cost. We introduce a novel approach to evaluate the approximation ratio of local search algorithms for these problems. This involves an adapted clustering method that captures pertinent information about outliers within both local and global optimal solutions. For k-MeaP, we enhance the best-known approximation ratio derived from local search, elevating it from 25 + epsilon to 9 + epsilon. The best-known approximation ratio for k-MedP is also obtained. Regarding k-MedO/k-MeaO, only two bi-criteria approximation algorithms based on local search exist. One violates the outlier constraint (limiting outlier count), while the other breaches the cardinality constraint (restricting the number of clusters). We focus on the former algorithm, enhancing its approximation ratios from 17+epsilon to 3+epsilon for k-MedO and from 274 + epsilon to 9 + epsilon for k-MeaO.
This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP-nets). Its focus is on aggregating p...
详细信息
ISBN:
(纸本)1577358872
This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP-nets). Its focus is on aggregating preferences over so-called swaps, for which optimal solutions in general are already known to be of exponential size. We first analyze a trivial 2-approximation algorithm that simply outputs the best of the given input preferences, and establish a structural condition under which the approximation ratio of this algorithm is improved to 4/3. We then propose a polynomial-time approximation algorithm whose outputs are provably no worse than those of the trivial algorithm, but often substantially better. A family of problem instances is presented for which our improved algorithm produces optimal solutions, while, for any e, the trivial algorithm cannot attain a (2- epsilon)-approximation. These results may lead to the first polynomial-time approximation algorithm that solves the CP-net aggregation problem for swaps with an approximation ratio substantially better than 2.
Noncommutative constraint satisfaction problems (CSPs) are higher-dimensional operator extensions of classical CSPs. Their approximability remains largely unexplored. A notable example of a noncommutative CSP that is ...
详细信息
ISBN:
(纸本)9798331516758;9798331516741
Noncommutative constraint satisfaction problems (CSPs) are higher-dimensional operator extensions of classical CSPs. Their approximability remains largely unexplored. A notable example of a noncommutative CSP that is not solvable in polynomial time is NC-Max-3-Cut. We present a 0.864-approximation algorithm for this problem. Our approach extends to a broader class of both classical and noncommutative CSPs. We introduce three key concepts: approximate isometry, relative distribution, and generalized anticommutation, which may be of independent interest.
We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP ...
详细信息
We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP relaxation of the non-robust version of the problem, we derive approximation algorithms for the robust version under different types of uncertainty, including polyhedral and ellipsoidal uncertainty.
In this paper, we address the problem of constructing required subgraphs using stock pieces of fixed length (CRS-SPFL, for short), which is a new variant of the minimum-cost edge-weighted subgraph (MCEWS, for short) p...
详细信息
In this paper, we address the problem of constructing required subgraphs using stock pieces of fixed length (CRS-SPFL, for short), which is a new variant of the minimum-cost edge-weighted subgraph (MCEWS, for short) problem. Concretely, for the MCEWS problem Q, it is asked to choose a minimum-cost subset of edges from a given graph G such that these edges can form a required subgraph G'. For the CRS-SPFL problem Q ', these edges in such a required subgraph G ' are further asked to be constructed by plus using some stock pieces of fixed length L. The new objective, however, is to minimize the total cost to construct such a required subgraph G ', where the total cost is sum of the cost to purchase stock pieces of fixed length L and the cost to construct all edges in such a subgraph G '. We obtain the following three main results. (1) Given an alpha-approximation algorithm to solve the MCEWS problem, where alpha >= 1 (for the case alpha=1, the MCEWS problem Q is solved optimally by a polynomial-time exact algorithm), we design a 2 alpha-approximation algorithm and another asymptotic 7 alpha 4-approximation algorithm to solve the CRS-SPFL problem Q ', respectively;(2) When Q is the minimum spanning tree problem, we provide a 32-approximation algorithm and an AFPTAS to solve the problem Q ' of constructing a spanning tree using stock pieces of fixed length L, respectively;(3) When Q is the single-source shortest paths tree problem, we present a 32-approximation algorithm and an AFPTAS to solve the problem Q ' of constructing a single-source shortest paths tree using stock pieces of fixed length L, respectively.
We study two generalizations of classic clustering problems called dynamic ordered k -median and dynamic k-supplier, where the points that need clustering evolve over time, and we are allowed to move the cluster cente...
详细信息
We study two generalizations of classic clustering problems called dynamic ordered k -median and dynamic k-supplier, where the points that need clustering evolve over time, and we are allowed to move the cluster centers between consecutive time steps. In these dynamic clustering problems, the general goal is to minimize certain combinations of the service cost of points and the movement cost of centers, or to minimize one subject to some constraints on the other. We obtain a constant-factor approximation algorithm for dynamic ordered k-median under mild assumptions on the input. We give a 3-approximation for dynamic k-supplier and a multi-criteria approximation for its outlier version where some points can be discarded, when the number of time steps is two. We complement the algorithms with almost matching hardness results.(c) 2022 Elsevier Inc. All rights reserved.
Stochastic combinatorial optimization problems are usually defined as planning problems, which involve purchasing and allocating resources in order to meet uncertain needs. For example, network designers need to make ...
详细信息
Stochastic combinatorial optimization problems are usually defined as planning problems, which involve purchasing and allocating resources in order to meet uncertain needs. For example, network designers need to make their best guess about the future needs of the network and purchase capabilities accordingly. Facing uncertain in the future, we either "wait and see" changes, or postpone decisions about resource allocation until the requirements or constraints become realized. Specifically, in the field of stochastic combinatorial optimization, some inputs of the problems are uncertain, but follow known probability distributions. Our goal is to find a strategy that minimizes the expected cost. In this paper, we consider the two-stage finite-scenario stochastic set cover problem and the single sink rent-or-buy problem by presenting primal-dual based approximation algorithms for these two problems with approximation ratio 2 eta and 4.39, respectively, where eta is the maximum frequency of the element of the ground set in the set cover problem.
In this paper, we address the line-capacitated minimum Steiner tree problem (the Lc-MStT problem, for short), which is a variant of the (Euclidean) capacitated minimum Steiner tree problem and defined as follows. Give...
详细信息
In this paper, we address the line-capacitated minimum Steiner tree problem (the Lc-MStT problem, for short), which is a variant of the (Euclidean) capacitated minimum Steiner tree problem and defined as follows. Given a set X = (r(1), r(2),...,r(n)} of n terminals in R-2, a demand function d : X -> N and a positive integer C, we are asked to determine the location of a line l and a Steiner tree T-l to interconnect these n terminals in X and at least one point located on this line l such that the total demand of terminals in each maximal subtree (of TO connected to the line l, where the terminals in such maximal subtree are all located at the same side of this line l, does not exceed the bound C. The objective is to minimize total weight Sigma(e is an element of Tl) w(e) of such a Steiner tree T-l among all line-capacitated Steiner trees mentioned-above, where weight w(e) = 0 if two endpoints of that edge e is an element of T-l are located on the line l and otherwise weight w(e) is the Euclidean distance between two endpoints of that edge e is an element of T-l . In addition, when this line l is as an input in R-2 and Sigma(r is an element of X) d(r) <= C holds, we refer to this version as the 1-line-fixed minimum Steiner tree problem (the 1Lf-MStT problem, for short). We obtain three main results. (1) Given a rho(st )-approximation algorithm to solve the Euclidean minimum Steiner tree problem and a rho(1Lf)-approximation algorithm to solve the 1Lf-MStT problem, respectively, we design a (rho(st)rho(1Lf )+2)-approximation algorithm to solve the Lc-MStT problem. (2) Whenever demand of each terminal r is an element of X is less than c/2, we provide a (rho(1Lf) + 2)-approximation algorithm to resolve the Lc-MStT problem. (3) Whenever demand of each terminal r is an element of X is at least c/2, using the Edmonds' algorithm to solve the minimum weight perfect matching as a subroutine, we present an exact algorithm in polynomial time to resolve the Lc-MStT problem.
In the Steiner forest problem, we are given a set of terminal pairs and need to find the minimum cost subgraph that connects each of the terminal pairs together. Motivated by the recent work on greedy approximation al...
详细信息
In the Steiner forest problem, we are given a set of terminal pairs and need to find the minimum cost subgraph that connects each of the terminal pairs together. Motivated by the recent work on greedy approximation algorithms for the Steiner forest, we provide efficient implementations of existing approximation algorithms and conduct a thorough experimental study to characterize their performance. We consider several approximation algorithms: the influential primal-dual 2-approximation algorithm due to Agrawal, Klein, and Ravi, the greedy algorithm due to Gupta and Kumar, and a randomized algorithm based on probabilistic approximation by tree metrics. We also consider the simplest heuristic greedy algorithm for the problem, which picks the closest unconnected pair of terminals and connects it using the shortest path between the terminals in the current graph. To characterize the performance of the algorithms, we created a new library with more than one thousand Steiner forest problem instances and conducted an extensive experimental analysis on those instances. Our analysis reveals that for the majority of instances the primal-dual algorithm is the fastest among all the algorithms considered here, and obtains solutions that are very close to the optimal solutions obtained by solving the integer program formulation of the problem.
We consider connectivity augmentation problems in the Steiner setting, where the goal is to augment the edge-connectivity between a specified subset of terminal nodes. In the Steiner Augmentation of a Graph problem (k...
详细信息
暂无评论