Yinyu Ye

Geometric Rounding: A Dependent Rounding Scheme for Allocation Problems

  • Dongdong Ge
  • Yinyu Ye
  • Shuzhong Zhang
  • Simai He
  • Zizhuo Wang
    • Categories Applications - OR and Management Sciences, Approximation Algorithms

    This paper presents a general technique to develop approximation algorithms for allocation problems with integral assignment constraints. The core of the method is a randomized dependent rounding scheme, called geometric rounding, which yields termwise rounding ratios (in expectation), while emphasizing the strong correlation between events. We further explore the intrinsic geometric structure and general theoretical … 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

    A Path to the Arrow-Debreu Competitive Market Equilibrium

  • Yinyu Ye
    • Categories Complementarity and Variational Inequalities, Game Theory, Linear Programming Tags , ,

    We present polynomial-time interior-point algorithms for solving the Fisher and Arrow-Debreu competitive market equilibrium problems with linear utilities and $n$ players. Both of them have the arithmetic operation complexity bound of $O(n^4\log(1/\epsilon))$ for computing an $\epsilon$-equilibrium solution. If the problem data are rational numbers and their bit-length is $L$, then the bound to generate an … Read more

    A Note on Exchange Market Equilibria with Leontief’s Utility: Freedom of Pricing Leads to Rationality

  • Yinyu Ye
    • Categories Complementarity and Variational Inequalities, Game Theory Tags , ,

    We extend the analysis of [27] to handling more general utility functions: piece-wise linear functions, which include Leontief’s utility. We show that the problem reduces to the general analytic center model discussed in [27]. Thus, the same linear programming complexity bound applies to approximating the Fisher equilibrium problem with these utilities. More importantly, we show … Read more

    Semidefinite Programming Based Algorithms for Sensor Network Localization

  • Pratik Biswas
  • Yinyu Ye
  • Tzu-Chen Liang
  • Ta-Chung Wang
    • Categories Applications - Science and Engineering, Multidisciplinary Design Optimization, Semi-definite Programming Tags

    An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite … Read more

    Theory of Semidefinite Programming for Sensor Network Localization

  • Anthony Man-Cho So
  • Yinyu Ye
    • Categories Applications - Science and Engineering, Facility Planning and Design, Semi-definite Programming Tags ,

    We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior–point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we … 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

    A New Complexity Result on Solving the Markov Decision Problem

  • Yinyu Ye
    • Categories Linear Programming Tags , ,

    We present a new complexity result on solving the Markov decision problem (MDP) with $n$ states and a number of actions for each state, a special class of real-number linear programs with the Leontief matrix structure. We prove that, when the discount factor $\theta$ is strictly less than $1$, the problem can be solved in … Read more

    A Multi-Exchange Local Search Algorithm for the Capacitated Facility Location Problem

  • Bo Chen
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Network Optimization Tags , ,

    We present a multi-exchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between $3+2\sqrt{2}-\epsilon$ and $3+2\sqrt{2}+\epsilon$ for any given constant … Read more

    DSDP4 Software User Guide

  • Steven Benson
  • Yinyu Ye
    • Categories Semi-definite Programming Tags

    DSDP4 is an implementation of the dual-scaling algorithm for semidefinite program ming. New features in this version include a Lanczos procedure for determining the step size, more precise primal solutions, a parallel solver, and improved performance on the standard test suites. Citation ANL/MCS-TM-255; Mathematics and Computer Science Division; Argonne National Laboratory; Argonne, IL; March 2002 … Read more