Yotaro Takazawa

Approximation algorithm for the two-stage stochastic set multicover problem with simple resource

  • Yotaro Takazawa
    • Categories Approximation Algorithms, Stochastic Programming Tags , , ,

    We study a two-stage, finite-scenarios stochastic version of the set multicover problem, where there is uncertainty about a demand for each element to be covered and the penalty cost is imposed linearly on the shortfall in each demand. This problem is NP-hard and has an application in shift scheduling in crowdsourced delivery services. For this … 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

    Approximation algorithms for the covering-type k-violation linear program

  • Tomonari Kitahara
  • Shinji Mizuno
  • Yotaro Takazawa
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms Tags , , , ,

    We study the covering-type k-violation linear program where at most $k$ of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we present a simple (k+1)-approximation algorithm using a natural LP relaxation. We also show that the integrality gap of the … Read more

    An improved approximation algorithm for the covering 0-1 integer program

  • Tomonari Kitahara
  • Shinji Mizuno
  • Yotaro Takazawa
    • Categories Approximation Algorithms Tags , ,

    We present an improved approximation algorithm for the covering 0-1 integer program (CIP), a well-known problem as a natural generalization of the set cover problem. Our algorithm uses a primal-dual algorithm for CIP by Fujito (2004) as a subroutine and achieves an approximation ratio of (f- (f-1)/m) when m is greater than or equal to … Read more

    An approximation algorithm for the partial covering 0-1 integer program

  • Tomonari Kitahara
  • Shinji Mizuno
  • Yotaro Takazawa
    • Categories Approximation Algorithms Tags , ,

    The partial covering 0-1 integer program (PCIP) is a relaxed problem of the covering 0-1 integer program (CIP) such that some fixed number of constraints may not be satisfied. This type of relaxation is also discussed in the partial set multi-cover problem (PSMCP) and the partial set cover problem (PSCP). In this paper, we propose … Read more

    A 2-approximation algorithm for the minimum knapsack problem with a forcing graph

  • Shinji Mizuno
  • Yotaro Takazawa
    • Categories Approximation Algorithms Tags , , ,

    Carnes and Shmoys (2015) presented a 2-approximation algorithm for the minimum knapsack problem. We extend their algorithm to the minimum knapsack problem with a forcing graph (MKPFG), which has a forcing constraint for each edge in the graph. The forcing constraint means that at least one item (vertex) of the edge must be packed in … Read more