Approximation Algorithms

A novel elitist multiobjective optimization algorithm: multiobjective extremal optimization

  • Min-Rong Chen
  • Yong-Zai Lu
    • Categories Approximation Algorithms, Meta Heuristics, Multi-Criteria Optimization

    Recently, a general-purpose local-search heuristic method called Extremal Optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in multiobjective optimization and proposes a new novel elitist multiobjective algorithm, called Multiobjective Extremal Optimization (MOEO). In order to extend EO to solve the multiobjective … Read more

    Polynomial time algorithms to approximate mixed volumes within a simply exponential factor

  • Leonid Gurvits
    • Categories Approximation Algorithms, Convex Optimization Tags , , ,

    We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets. Our main result is a randomized poly-time algorithm which approximates $V(K_1,…,K_n)$ with multiplicative error $e^n$ and with better rates if the affine dimensions of most of the sets $K_i$ are small.\\ Even such rate is impossible to achieve … Read more

    Approximation algorithms for metric tree cover and generalized tour and tree covers

  • Viet Hung Nguyen
    • Categories Approximation Algorithms, Network Optimization, Polyhedra Tags , , , ,

    Given a weighted undirected graph $G=(V,E)$, a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of $G$. Arkin, Halld\’orsson … Read more

    A Unified Theorem on SDP Rank Reduction

  • Anthony Man-Cho So
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Semi-definite Programming Tags ,

    We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices. Specifically, let $A_1,\ldots,A_m \in \R^{n\times n}$ be symmetric, positive semidefinite matrices, and let $b_1,\ldots,b_m \ge 0$. We show that if there exists a symmetric, positive semidefinite matrix $X$ to the system $A_i \bullet X … Read more

    An Approximation Algorithm for Constructing Error Detecting Prefix Codes

  • Artur Alves Pessoa
    • Categories Approximation Algorithms, Telecommunications Tags , ,

    A $k$-bit Hamming prefix code is a binary code with the following property: for any codeword $x$ and any prefix $y$ of another codeword, both $x$ and $y$ having the same length, the Hamming distance between $x$ and $y$ is at least $k$. Given an alphabet $A = [a_1,\ldots,a_n]$ with corresponding probabilities $[p_1,\ldots,p_n]$, the $k$-bit … Read more

    On complexity of Shmoys – Swamy class of two-stage linear stochastic programming problems

  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Approximation Algorithms, Stochastic Programming Tags , ,

    We consider a class of two-stage linear stochastic programming problems, introduced by Shmoys and Swamy (2004), motivated by a relaxation of a stochastic set cover problem. We show that the sample size required to solve this problem by the sample average approximation (SAA) method with a relative accuracy $\kappa>0$ and confidence $1-\alpha$ is polynomial in … Read more

    Approximating the Radii of Point Sets

  • Kasturi Varadarajan
  • S Venkatesh
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Data-Mining, Semi-definite Programming Tags ,

    We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers $n, d, k$ where $k \le d$, and a set $P$ of $n$ points in $R^d$. The goal is to compute the {\em outer $k$-radius} of $P$, denoted by $\kflatr(P)$, which is the minimum, over all $(d-k)$-dimensional … Read more

    Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures :\

  • Leonid Gurvits
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

    The paper describes various combinatorial and algorithmic applications of hyperbolic (multivariate) polynomials . Section 2.2 introduces a new class of polynomials , which include as hyperbolic polynomials as well volume polynomials $Vol(x_1C_1+…+x_nC_n)$ , where $C_i$ are convex compact subsets of $R^n$. This extension leads to randomized poly-time algorithm to approximate $M(C_1,…,C_n)$ (the mixed volume) within … Read more

    Solving a combinatorial problem using a local optimization in ant based system

  • D. Dumitrescu
  • C-M. Pintea
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    Local optimizations introduced to obtain improved tours for Traveling Salesman Problem have a great impact on the final solution. That is way we introduce a new ant system algorithm with a new local updating pheromone rule, and the tours are improved using k-opt techniques. The tests use different parameters, in order to obtain solutions close … Read more

    A copositive programming approach to graph partitioning

  • Janez Povh
  • Franz Rendl
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , ,

    We consider 3-partitioning the vertices of a graph into sets $S_1, S_2$ and $S_3$ of specified cardinalities, such that the total weight of all edges joining $S_1$ and $S_2$ is minimized. This problem is closely related to several NP-hard problems like determining the bandwidth or finding a vertex separator in a graph. We show that … Read more