Главная

Yinyu Ye

  1. Complexity of Unconstrained L_2-L_p Minimization.

    Ср, 05/04/2011 - 15:01 — SomNambul
    Authors: Zizhuo Wang, Yinyu Ye, Xiaojun Chen, Dongdong Ge
    Subjects: Computational Complexity
    Abstract

    We consider the unconstrained $L_2$-$L_p$ minimization: find a minimizer of
    $\|Ax-b\|^2_2+\lambda \|x\|^p_p$ for given $A \in R^{m\times n}$, $b\in R^m$
    and parameters $\lambda>0$, $p\in [0,1)$. This problem has been studied
    extensively in variable selection and sparse least squares fitting for high
    dimensional data. Theoretical results show that the minimizers of the
    $L_2$-$L_p$ problem have various attractive features due to the concavity and
    non-Lipschitzian property of the regularization function $\|\cdot\|^p_p$.

  2. Close the Gaps: A Learning-while-Doing Algorithm for a Class of Single-Product Revenue Management Problems.

    Ср, 01/26/2011 - 16:01 — SomNambul
    Authors: Zizhuo Wang, Yinyu Ye, Shiming Deng
    Subjects: Learning
    Abstract

    We present a dynamic learning algorithm for a class of single-product revenue
    management problems. In these problems, a retailer sells a single product with
    limited on-hand inventory over a finite selling season. Customer demand arrives
    according to a Poisson process, the rate of which is influenced by a single
    action taken by the retailer (such as price adjustment, sales commission,
    advertisement intensity, etc.). The relation between the action and the demand
    rate is not known in advance.

  3. On Sensor Network Localization Using SDP Relaxation.

    Ср, 10/13/2010 - 15:01 — SomNambul
    Authors: Yinyu Ye, Nicole Taheri, Davood Shamsi
    Subjects: Metric Geometry
    Abstract

    Sensor network localization attempts to determine the locations of a group of
    sensors given the distances between some of them. The Semidefinite Programming
    (SDP) relaxation of this problem is widely used to determine the locations of
    the sensors. In this paper, we analyze and determine a number of conditions
    that guarantee that the SDP relaxation is exact, i.e. gives the correct
    solution. Our main contribution is twofold. We present the first non-asymptotic
    bound on the connectivity range requirement of the sensors in order to ensure
    the network is uniquely localizable.

  4. On affine motions and bar frameworks in general position.

    Пнд, 09/20/2010 - 15:01 — SomNambul
    Authors: Yinyu Ye, A. Y. Alfakih
    Subjects: Metric Geometry
    Abstract

    A configuration p in r-dimensional Euclidean space is a finite collection of
    points (p^1,...,p^n) that affinely span R^r. A bar framework, denoted by G(p),
    in R^r is a simple graph G on n vertices together with a configuration p in
    R^r.

  5. Toward the Universal Rigidity of General Frameworks.

    Ср, 09/08/2010 - 15:01 — SomNambul
    Authors: Yinyu Ye, Abdo Y. Alfakih, Nicole Taheri
    Subjects: Metric Geometry
    Abstract

    We prove that the (d+1)-lateration graph with n(>= d+1) point, when points
    are in general position in R^d, not only is universally rigid, but also admits
    a rank (n-d-1) positive semi-definite stress matrix. We also prove that a
    similar result holds as in the case of sensor network localization when the
    graph has m(>= d+1) anchors.

  6. A Dynamic Near-Optimal Algorithm for Online Linear Programming.

    Втр, 11/17/2009 - 16:01 — SomNambul
    Authors: Shipra Agrawal, Zizhuo Wang, Yinyu Ye
    Subjects: Computer Science and Game Theory
    Abstract

    We consider the online linear programming problem where the constraint matrix
    is revealed column by column along with the objective function. We provide a
    1-o(1) competitive algorithm for this surprisingly general class of online
    problems under the assumption of random order of arrival and some mild
    conditions on the right-hand-side input. Our learning-based algorithm works by
    dynamically updating a threshold price vector at geometric time intervals, the
    price learned from the previous steps is used to determine the decision for the
    current step.

Math-arch

RSS-материал