Piyush Kumar

A Linearly Convergent Linear-Time First-Order Algorithm for Support Vector Classification with a Core Set Result

  • Piyush Kumar
  • E. Alper Yildirim
    • Categories Convex Optimization Tags , , , , ,

    We present a simple, first-order approximation algorithm for the support vector classification problem. Given a pair of linearly separable data sets and $\epsilon \in (0,1)$, the proposed algorithm computes a separating hyperplane whose margin is within a factor of $(1-\epsilon)$ of that of the maximum-margin separating hyperplane. We discuss how our algorithm can be extended … Read more

    An Algorithm and a Core Set Result for the Weighted Euclidean One-Center Problem

  • Piyush Kumar
  • E. Alper Yildirim
    • Categories Convex Optimization Tags , , ,

    Given ${\cal A} := \{a^1,\ldots,a^m\} \subset \R^n$ with corresponding positive weights ${\cal W} := \{\omega_1,\ldots,\omega_m\}$, the weighted Euclidean one-center problem, which is a generalization of the minimum enclosing ball problem, involves the computation of a point $c_{\cal A} \in \R^n$ that minimizes the maximum weighted Euclidean distance from $c_{\cal A}$ to each point in ${\cal … Read more

    Computing Minimum Volume Enclosing Axis-Aligned Ellipsoids

  • Piyush Kumar
  • E. Alper Yildirim
    • Categories Convex Optimization, Nonlinear Optimization Tags , , ,

    Given a set of points $\cS = \{x^1,\ldots,x^m\} \subset \R^n$ and $\eps > 0$, we propose and analyze an algorithm for the problem of computing a $(1 + \eps)$-approximation to the the minimum volume axis-aligned ellipsoid enclosing $\cS$. We establish that our algorithm is polynomial for fixed $\eps$. In addition, the algorithm returns a small … Read more