Approximation Algorithms

A Feasible method for Optimization with Orthogonality Constraints

  • Zaiwen Wen
  • Wotao Yin
    • Categories Approximation Algorithms, Nonlinear Optimization Tags , , , , , , , , , ,

    Minimization with orthogonality constraints (e.g., $X^\top X = I$) and/or spherical constraints (e.g., $\|x\|_2 = 1$) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. … Read more

    Burer’s Key Assumption for Semidefinite and Doubly Nonnegative Relaxations

  • Florian Jarre
    • Categories Approximation Algorithms, Quadratic Programming, Semi-definite Programming Tags , ,

    Burer has shown that completely positive relaxations of nonconvex quadratic programs with nonnegative and binary variables are exact when the binary variables satisfy a so-called key assumption. Here we show that introducing binary variables to obtain an equivalent problem that satisfies the key assumption will not improve the semidefinite relaxation, and only marginally improve the … Read more

    Local Search Approximation Algorithms for the Complement of the Min-hBcCut Problems

  • Wenxing Zhu
    • Categories Approximation Algorithms Tags , ,

    Min-$k$-cut is the problem of partitioning vertices of a given graph or hypergraph into $k$ subsets such that the total weight of edges or hyperedges crossing different subsets is minimized. For the capacitated min-$k$-cut problem, each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on … Read more

    Feasible and accurate algorithms for covering semidefinite programs

  • Garud Iyengar
  • Cliff Stein
  • David Phillips
    • Categories Approximation Algorithms, Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    In this paper we describe an algorithm to approximately solve a class of semidefinite programs called covering semidefinite programs. This class includes many semidefinite programs that arise in the context of developing algorithms for important optimization problems such as sparsest cut, wireless multicasting, and pattern classification. We give algorithms for covering SDPs whose dependence on … Read more

    Approximating the Least Core Value and Least Core of Cooperative Games with Supermodular Costs

  • Andreas S. Schulz
  • Nelson A. Uhan
    • Categories Approximation Algorithms, Game Theory, Graphs and Matroids

    We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a (3 + \epsilon)-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time … Read more

    Approximating the minimum directed tree cover

  • Viet Hung Nguyen
    • Categories 0-1 Programming, Approximation Algorithms, Telecommunications Tags , , ,

    Given a directed graph $G$ with non negative cost on the arcs, a directed tree cover of $G$ is a directed tree such that either head or tail (or both of them) of every arc in $G$ is touched by $T$. The minimum directed tree cover problem (DTCP) is to find a directed tree cover … Read more

    Intractability of approximate multi-dimensional nonlinear optimization on independence systems

  • Shmuel Onn
  • Robert Weismantel
  • Jon Lee
    • Categories Approximation Algorithms, Graphs and Matroids, Multi-Criteria Optimization Tags , ,

    We consider optimization of nonlinear objective functions that balance $d$ linear criteria over $n$-element independence systems presented by linear-optimization oracles. For $d=1$, we have previously shown that an $r$-best approximate solution can be found in polynomial time. Here, using an extended Erdos-Ko-Rado theorem of Frankl, we show that for $d=2$, finding a $\rho n$-best solution … Read more

    The minimum spanning tree problem with conflict constraints and its variations

  • Santosh N. Kabadi
  • Abraham Punnen
  • R. Zhang
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

    We consider the minimum spanning tree problem with conflict constraints (MSTC). It is observed that computing an $\epsilon$-optimal solution to MSTC is NP-hard for any $\epsilon >0$. For a general conflict graph, computing even a feasible solution is NP-hard. When the underlying graph is a cactus, we show that the feasibility problem is polynomially bounded … Read more

    Approximating the asymmetric profitable tour

  • Viet Hung Nguyen
  • Thi Thu Thuy Nguyen
    • Categories 0-1 Programming, Approximation Algorithms, Network Optimization Tags , , ,

    We study the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. In \cite{Amico}, the authors … Read more

    A Spectral Algorithm for Improving Graph Partitions

  • Michael W. Mahoney
  • Lorenzo Orecchia
  • Nisheeth K. Vishnoi
    • Categories Approximation Algorithms Tags ,

    In the cut-improvement problem, we are asked, given a starting cut (T,V\T) in a graph G, to find a cut with low conductance around(T, V\T) or produce a certificate that there is none. More precisely, for a notion of correlation between cuts, cut-improvement algorithms seek to produce approximation guarantees of the following form: for any … Read more