Approximation Algorithms

A Polynomial-time Algorithm with Tight Error Bounds for Single-period Unit Commitment Problem

  • S.C. Fang
  • Ruotian Gao
  • Wenxun Xing
  • Cheng Lu
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Scheduling Tags , , , ,

    This paper proposes a Lagrangian dual based polynomial-time approximation algorithm for solving the single-period unit commitment problem, which can be formulated as a mixed integer quadratic programming problem and proven to be NP-hard. Tight theoretical bounds for the absolute errors and relative errors of the approximate solutions generated by the proposed algorithm are provided. Computational … Read more

    Query Batching Optimization in Database Systems

  • Hadi Charkhgard
  • Iman Dayarian
  • Mehrad Eslami
  • Vahid Mahmoodian
  • Yicheng Tu
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Multidisciplinary Design Optimization

    Techniques based on sharing data and computation among queries have been an active research topic in database systems. While work in this area developed algorithms and systems that are shown to be effective, there is a lack of rigorous modeling and theoretical study for query processing and optimization. Query batching in database systems has strong … Read more

    Scheduling Post-disaster Repairs in Electricity Distribution Networks with Uncertain Repair Times

  • Mareldi Ahumada-Paras
  • Payman Arabshahi
  • Arindam Das
  • Daniel Kirschen
  • Yushi Tan
    • Categories Approximation Algorithms, Energy, Scheduling Tags , , ,

    Natural disasters, such as hurricanes, large wind and ice storms, typically require the repair of a large number of components in electricity distribution networks. Since power cannot be restored before the completion of repairs, optimally scheduling the available crews to minimize the cumulative duration of the customer interruptions reduces the harm done to the affected … Read more

    Minimizing Total Earliness and Tardiness with Periodically Supplied Non-renewable Resource Profiles

  • Aleida Braaksma
  • Mohammad Mahdavi Mazdeh
  • Mohammad Namakshenas
    • Categories Approximation Algorithms, Scheduling Tags , , ,

    We consider a special class of resource-constrained single machine scheduling problems. In the classical scheduling context, resource types are classi ed into renewable and non-renewable; however, a large variety of real-world problems may not fit into one of these classes, e.g., labor regulations in project scheduling, budget allocation to different phases of a construction project, and … Read more

    An analysis of noise folding for low-rank matrix recovery

  • Wang Hailin
  • Jianjun Wang
  • Jianwen Huang
  • Wang Wendong
  • Feng Zhang
    • Categories Approximation Algorithms, Convex Optimization, Data-Mining

    Previous work regarding low-rank matrix recovery has concentrated on the scenarios in which the matrix is noise-free and the measurements are corrupted by noise. However, in practical application, the matrix itself is usually perturbed by random noise preceding to measurement. This paper concisely investigates this scenario and evidences that, for most measurement schemes utilized in … Read more

    Scheduling jobs with a V-shaped time-dependent processing time

  • Helmut Sedding
    • Categories Approximation Algorithms, Scheduling

    In the field of time-dependent scheduling, a job’s processing time is specified by a function of its start time. While monotonic processing time functions are well-known in the literature, this paper introduces non-monotonic functions with a convex, piecewise-linear V-shape similar to the absolute value function. They are minimum at an ideal start time, which is … Read more

    A faster FPTAS for counting two-rowed contingency tables

  • Tzvi Alon
  • Nir Halman
    • Categories Approximation Algorithms, Dynamic Programming Tags , , ,

    In this paper we provide a deterministic fully polynomial time approximation scheme (FPTAS) for counting two-rowed contingency tables that is faster than any either deterministic or randomized approximation scheme for this problem known to date. Our FPTAS is derived via a somewhat sophisticated usage of the method of K-approximation sets and functions introduced by Halman … Read more

    A gradient type algorithm with backward inertial steps for a nonconvex minimization

  • Cristian Alecsa
  • Laszlo Szilard Csaba
  • Adrian Viorel
    • Categories Approximation Algorithms, Convex and Nonsmooth Optimization Tags , , ,

    We investigate an algorithm of gradient type with a backward inertial step in connection with the minimization of a nonconvex differentiable function. We show that the generated sequences converge to a critical point of the objective function, if a regularization of the objective function satis es the Kurdyka-Lojasiewicz property. Further, we provide convergence rates for the … Read more

    An Efficient Linear Programming Based Method for the Influence Maximization Problem in Social Networks

  • Evren Güney
    • Categories 0-1 Programming, Approximation Algorithms, Network Optimization Tags , , ,

    The influence maximization problem (IMP) aims to determine the most influential individuals within a social network. In this study first we develop a binary integer program that approximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently, we propose a linear programming relaxation based method with a provable worst case bound that … Read more

    On a reduction of the weighted induced bipartite subgraph problem to the weighted independent set problem

  • Shinji Mizuno
  • Yotaro Takazawa
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

    We study the weighted induced bipartite subgraph problem (WIBSP). The goal of WIBSP is, given a graph and nonnegative weights for the nodes, to find a set W of nodes with the maximum total weight such that a subgraph induced by W is bipartite. WIBSP is also referred as to the graph bipartization problem or … Read more