divide-and-conquer

A new combinatorial algorithm for separable convex resource allocation with nested bound constraints

  • Qie He
  • Kameng Nip
  • Zeyang Wu
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , , ,

    The separable convex resource allocation problem with nested bound constraints aims to allocate $B$ units of resources to $n$ activities to minimize a separable convex cost function, with lower and upper bounds on the total amount of resources that can be consumed by nested subsets of activities. We develop a new combinatorial algorithm to solve … Read more

    An SDP-based divide-and-conquer algorithm for large scale noisy anchor-free graph realization

  • Ngai-Hang Z. Leung
  • Kim-Chuan Toh
    • Categories Basic Sciences Applications, Global Optimization Applications, Semi-definite Programming Tags , , ,

    We propose the DISCO algorithm for graph realization in $\real^d$, given sparse and noisy short-range inter-vertex distances as inputs. Our divide-and-conquer algorithm works as follows. When a group has a sufficiently small number of vertices, the basis step is to form a graph realization by solving a semidefinite program. The recursive step is to break … Read more