Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.orl.2022.01.004

researchmap

Publishing type：Research paper (international conference proceedings)  

researchmap

Other Link： https://dblp.uni-trier.de/rec/conf/aaai/2022

Authorship：Lead author   Language：English   Publishing type：Research paper (scientific journal)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer International Publishing  

DOI： 10.1007/978-3-030-67664-3_12

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

researchmap

Other Link： https://dblp.uni-trier.de/rec/conf/aaai/2021

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：PMLR  

researchmap

Other Link： https://dblp.uni-trier.de/conf/aistats/2021

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Information Processing Society of Japan  

DOI： 10.2197/ipsjjip.29.216

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Other Link： https://dblp.uni-trier.de/db/journals/corr/corr2101.html#abs-2101-07957

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Institute of Electrical and Electronics Engineers (IEEE)  

DOI： 10.1109/tnet.2019.2963361

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

DOI： 10.1109/PDP50117.2020.00017

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/pdp/pdp2020.html#IgarashiKFA20

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Other Link： https://dblp.uni-trier.de/conf/nips/2020

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

DOI： 10.1109/ICESS49830.2020.9301600

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/icess/icess2020.html#KoikeFIA20

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier  

DOI： 10.1016/j.tcs.2019.05.018

arXiv

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1137/18M117442

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s10878-018-0354-y

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

DOI： 10.1609/aaai.v33i01.33011485

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/aaai/aaai2019.html#FukunagaKFK19

Publishing type：Research paper (scientific journal)   Publisher：Springer Science and Business Media LLC  

DOI： 10.1007/s00453-017-0385-2

researchmap

Other Link： http://link.springer.com/content/pdf/10.1007/s00453-017-0385-2.pdf

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-319-94776-1_5

researchmap

Publishing type：Research paper (international conference proceedings)  

researchmap

Other Link： http://dblp.uni-trier.de/db/conf/nips/nips2018.html#conf/nips/ItoHSYFKK18

Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-319-98809-2_26

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：PMLR  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-319-77404-6_48

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：JMLR.org  

researchmap

Other Link： http://dblp.uni-trier.de/db/conf/icml/icml2018.html#conf/icml/YabeHSIKFK18

Language：English   Publishing type：Research paper (scientific journal)  

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/talg/talg13.html#journals/talg/Fukunaga17

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

We consider an optimization problem for finding efficient placement of virtual machines (VMs) in a data center network. In this problem, we receive requests of VMs from customers, and seek to determine those physical machines in the network that host the requested VMs under capacity constraints. The objective of the problem is to minimize the total connection cost of the VM placement. We propose two models of the connection cost, called the centralized and the distributed models. In the former model, the connection cost for each request is defined as the minimum length of networks connecting all physical host machines and a specified root node, while the network does not connect the root node in the latter model. We present approximation algorithms for this optimization problem. For the centralized model, we present an O(log theta)-approximation algorithm, where theta is the ratio of the largest to the smallest requests. For the distributed model with uniform requests, we present an O(logn)-approximation algorithm for networks on n nodes. We also present a heuristic-based algorithm for the distributed model with non-uniform requests, and verify the performance of our algorithms through computational experiments. (C) 2017 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disopt.2017.05.004

Web of Science

researchmap

Publisher：ijcai.org  

DOI： 10.24963/ijcai.2017/60

researchmap

researchmap

Other Link： http://dblp.uni-trier.de/db/conf/nips/nips2017.html#conf/nips/ItoHSYFKK17

Language：English  

DOI： 10.1007/978-981-10-6147-9

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

researchmap

Other Link： http://dblp.uni-trier.de/db/conf/aaai/aaai2017.html#conf/aaai/HatanoFMK17

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

This paper discusses the graph covering problem in which a set of edges in an edge- and node-weighted graph is chosen to satisfy some covering constraints while minimizing the sum of the weights. In this problem, because of the large integrality gap of a naive linear programming (LP) relaxation, LP rounding algorithms based on the relaxation yield poor performance. Here we propose a stronger LP relaxation for the graph covering problem. The proposed relaxation is applied to designing primal dual algorithms for two fundamental graph covering problems: the prize-collecting edge dominating set problem and the multicut problem in trees. Our algorithms are an exact polynomial-time algorithm for the former problem, and a 2-approximation algorithm for the latter problem. These results match the currently known best results for purely edge-weighted graphs. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disopt.2016.03.001

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SIAM PUBLICATIONS  

We consider a network design problem called the generalized terminal backup problem. Whereas earlier work investigated the edge-connectivity constraints only, we consider both edge-and node-connectivity constraints for this problem. A major contribution of this paper is the development of a strongly polynomial-time 4/3-approximation algorithm for the problem. Specifically, we show that a linear programming relaxation of the problem is half-integral, and that the half-integral optimal solution can be rounded to a 4/3-approximate solution. We also prove that the linear programming relaxation of the problem with the edge-connectivity constraints is equivalent to minimizing the cost of half-integral multiflows that satisfy flow demands given from terminals. This observation implies a strongly polynomial-time algorithm for computing a minimum cost half-integral multiflow under flow demand constraints.

DOI： 10.1137/151004288

Web of Science

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：IJCAI/AAAI Press  

researchmap

Other Link： http://dblp.uni-trier.de/db/conf/ijcai/ijcai2016.html#conf/ijcai/HatanoFK16

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

In this paper, we consider a new Steiner tree problem. This problem defines the weight of a Steiner tree as the minimum weight of vertex covers in the tree, and seeks a minimum-weight Steiner tree in a given vertex-weighted undirected graph. Since it is included by the Steiner tree activation problem, the problem admits an O(log n)- approximation algorithm in general graphs with n vertices. This approximation factor is tight because it is known to be NP-hard to achieve an o(log n)-approximation for the problem with general graphs. In this paper, we present constant-factor approximation algorithms for the problem with unit disk graphs and with graphs excluding a fixed minor.

DOI： 10.1007/978-3-319-48749-6_6

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

We consider a network design problem called the generalized terminal backup problem. Whereas earlier work investigated the edge-connectivity constraints only, we consider both edge- and nodeconnectivity constraints for this problem. A major contribution of this paper is the development of a strongly polynomial-time 4/3-approximation algorithm for the problem. Specifically, we show that a linear programming relaxation of the problem is half-integral, and that the half-integral optimal solution can be rounded to a 4/3-approximate solution. We also prove that the linear programming relaxation of the problem with the edge-connectivity constraints is equivalent to minimizing the cost of half-integral multiflows that satisfy flow demands given from terminals. This observation implies a strongly polynomial-time algorithm for computing a minimum cost half-integral multiflow under flow demand constraints.

DOI： 10.4230/LIPIcs.STACS.2015.316

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SIAM PUBLICATIONS  

We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset linear programming relaxation for this problem. For directed graphs and k-out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node v in the solution is at most 2b(v) + O(k), where b(v) is the degree upper bound on v. For undirected graphs and element-connectivity requirements with maximum connectivity requirement k, our algorithm computes a solution that is a 4-approximation on the cost, and the degree of each node v in the solution is at most 4b(v) + O(k). These ratios improve the previous O(log k)-approximation on the cost and O(2(k)b(v))-approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected k-out-connectivity, directed and undirected k-connectivity, and undirected rooted k-connectivity and subset k-connectivity.

DOI： 10.1137/13094503X

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：JMLR.org  

researchmap

Other Link： http://dblp.uni-trier.de/db/conf/icml/icml2015.html#conf/icml/MiyauchiIFK15

Publisher：SIAM  

DOI： 10.1137/1.9781611973730.2

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

Virtualization is a key technology for the efficient operation of massive data centers. To minimize the communication costs among virtual machines (VMs) in a data center network, we formulate an optimization problem for finding efficient VM placements. In this problem, a set of requests is received from customers, where each request is defined as the required number of VMs. The problem seeks to determine those physical machines in the network that host the requested VMs under a capacity constraint such that the number of VMs placed on each physical machine does not exceed that of the available slots. To minimize the load of the networks, for each request, we consider the connection cost of the VM placements, which is defined as the minimum length of networks connecting all physical host machines and the root node. The objective in the problem is to minimize the total connection costs. We present an approximation algorithm for this optimization problem.

DOI： 10.1109/INFCOMW.2015.7179432

Web of Science

researchmap

Publisher：AAAI Press  

researchmap

Other Link： http://dblp.uni-trier.de/db/conf/aaai/aaai2015.html#conf/aaai/HatanoFMK15

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

The inventory routing problem involves trading off inventory holding costs at client locations with vehicle routing costs to deliver frequently from a single central depot to meet deterministic client demands over a finite planing horizon. In this paper, we consider periodic solutions that visit clients in one of several specified frequencies, and focus on the case when the frequencies of visiting nodes are nested. We give the first constant-factor approximation algorithms for designing optimum nested periodic schedules for the problem with no limit on vehicle capacities by simple reductions to prize-collecting network design problems. For instance, we present a 2.55-approximation algorithm for the minimum-cost nested periodic schedule where the vehicle routes are modeled as minimum Steiner trees. We also show a general reduction from the capacitated problem where all vehicles have the same capacity to the uncapacitated version with a slight loss in performance. This reduction gives a 4.55-approximation for the capacitated problem. In addition, we prove several structural results relating the values of optimal policies of various types.

DOI： 10.4230/LIPIcs.APPROX-RANDOM.2014.209

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier B.V.  

An unranking algorithm for a finite set Sis an algorithm that, given a number in {0, 1, ..., |S| -1}, returns an element of Sthat is associated with the number. We suppose that a number can be associated with any element in Sso long as distinct elements are associated with different numbers. A ranking algorithm is the reverse of an unranking algorithm. In this paper, we present an unranking algorithm for the set of all m-element subsets of an n-element set. Our algorithm runs with O(m3m+3)arithmetic operations, which is independent of nand hence is effective when nis large. We also show that it admits a ranking algorithm with the same running time.

DOI： 10.1016/j.jda.2014.07.004

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

This paper discusses the graph covering problem in which a set of edges in an edge-and node-weighted graph is chosen to satisfy some covering constraints while minimizing the sum of the weights. In this problem, because of the large integrality gap of a natural linear programming (LP) relaxation, LP rounding algorithms based on the relaxation yield poor performance. Here we propose a stronger LP relaxation for the graph covering problem. The proposed relaxation is applied to designing primal-dual algorithms for two fundamental graph covering problems: the prize-collecting edge dominating set problem and the multicut problem in trees. Our algorithms are an exact polynomial-time algorithm for the former problem, and a 2-approximation algorithm for the latter problem, respectively. These results match the currently known best results for purely edge-weighted graphs.

DOI： 10.1007/978-3-319-08404-6_19

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

The hypergraph k-cut problem is the problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into at least k connected components. We present an algorithm for this problem, that runs in strongly polynomial time if both k and the maximum size of the hyperedges are constants. Our algorithm extends the algorithm proposed by Thorup (2008) for computing minimum k-cuts of graphs from greedy packings of spanning trees. (C) 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disopt.2013.10.002

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

In the source location problem, the goal is to compute a minimum cost source set in a graph so that the connectivity between the source set and each vertex is at least the demand of the vertex. In this paper, we consider the problem for undirected graphs, and the connectivity between a source set S and a vertex v is defined as the maximum number of paths between v and S no two of which have common vertex except v. We give an O(d*log d*)- approximation algorithm for the problem with maximum demand d*. We also define a variant of the source location problem and give an approximation algorithm for it. © 2013 Elsevier B.V.

DOI： 10.1016/j.jda.2013.02.002

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

In an undirected or a directed graph, the edge-connectivity between two disjoint vertex sets X and Y is defined as the minimum number of edges or arcs that should be removed for disconnecting all vertices in Y from those in X. This paper discusses how to construct a directed graph from a given undirected graph by orienting edges so as to preserve the edge-connectivity on pairs of vertex sets as much as possible. We present several bounds on the gap between the edge-connectivities in the undirected graph and in the obtained directed graphs, which extends the Nash-Williams' strong orientation theorem. (C) 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2012.04.004

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

The submodular system k-partition problem is a problem of partitioning a given finite set V into k non-empty subsets V (1),V (2),aEuro broken vertical bar,V (k) so that E-i=1(k) f(V-i) is minimized where f is a non-negative submodular function on V. In this paper, we design an approximation algorithm for the problem with fixed k. We also analyze the approximation factor of our algorithm for the hypergraph k-cut problem, which is a problem contained by the submodular system k-partition problem.

DOI： 10.1007/s00453-010-9483-0

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

We consider the problem of finding a minimum edge cost subgraph of an undirected or a directed graph satisfying given connectivity requirements and degree bounds b(.) on nodes. We present an iterative rounding algorithm for this problem. When the graph is undirected and the connectivity requirements are on the element-connectivity with maximum value k, our algorithm computes a solution that is an O(k)-approximation for the edge cost in which the degree of each node v is at most O(k) . b(v). We also consider the no edge cost case where the objective is to find a subgraph satisfying connectivity requirements and degree bounds. Our algorithm for this case outputs a solution in which the degree of each node v is at most 6 . b(v) + O(k(2)). These algorithms can be extended to other well-studied undirected node-connectivity requirements such as uniform, subset and rooted connectivity. When the graph is directed and the connectivity requirement is k-out-connectivity from a root, our algorithm computes a solution that is a 2-approximation for the edge cost in which the degree of each node v is at most 2 . b(v) + O(k).

DOI： 10.1109/FOCS.2012.30

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：WORLD SCIENTIFIC PUBL CO PTE LTD  

This paper considers a problem of locating the given number of disks into a container no that the area covered by the disks is maximized. In the problem, the radii of the disks can be changed arbitrarily unless they overlap outside of the container, and the disks are allowed to overlap with each other. We present an approximation algorithm for this problem assuming that the container is a convex polygon. Our algorithm achieves approximation ratio (0.78 - epsilon) for any small epsilon > 0. Since the computation tine of our algorithm depends on the number of corners of the convex polygon exponentially, we also give a heuristic to reduce the number of corners.

DOI： 10.1142/S0218195911003858

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER TOKYO  

An undirected graph G = (V, E) is called Z(3)-connected if for all b : V -> Z(3) with Sigma(nu is an element of V) b(v) = 0, an orientation D = (V, A) of G has a Z(3)-valued nowhere-zero flow f : A -> Z(3)-{0} such that Sigma(e is an element of delta+(nu)) f (e) - Sigma(e is an element of delta-(nu)) f (e) = b(nu) for all nu is an element of V. We show that all 4-edge-connected HHD-free graphs are Z3-connected. This extends the result due to Lai (Graphs Comb 16:165-176, 2000), which proves the Z(3)-connectivity for 4-edge-connected chordal graphs.

DOI： 10.1007/s00373-010-0995-9

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

The source location problem is a problem of computing a minimum cost source set in an undirected graph so that the connectivity between the source set and each vertex is at least the demand of the vertex. In this paper, the connectivity between a source set S and a vertex v is defined as the maximum number of paths between v and S no two of which have common vertices except v. We propose an O(d* log d*)approximation algorithm for the problem with maximum demand d*. We also define a variant of the source location problem and propose an approximation algorithm for it.

DOI： 10.1007/978-3-642-20877-5_42

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

In an undirected graph G = (V,E) with a weight function omega : E x V -> Q(+) the weighted degree d(omega)(upsilon; E) of a vertex v is defined as Sigma{omega(e,upsilon) | e epsilon E incident to upsilon}. In this paper, we consider a network design problem which has upper-bounds on weighted degrees of vertices as its constraints while the objective is to compute a minimum cost graph with a prescribed connectivity. We propose bi-criteria approximation algorithms based on iterative rounding, which has been successfully applied to the degree-bounded network design problem. A problem of minimizing the maximum weighted degree of vertices is also discussed. (C) 2010 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disopt.2010.05.004

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-642-14553-7_21

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

Hypergraph k-cut problem is a problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into k connected components. We present an algorithm for this problem which runs in strongly polynomial-time if both k and the rank of the hypergraph are constants. Our algorithm extends the algorithm clue to Thorup (2008) for computing minimum k-cuts of graphs from greedy packings of spanning trees.

DOI： 10.1007/978-3-642-13036-6_2

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer ka parts per thousand yen1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex vaV is equal to b(v). This problem generalizes metric TSP. In this paper, we show that the problem admits a rho-approximation algorithm if b(v)a parts per thousand yen2, vaV, where rho=2.5 if k is even, and rho=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.

DOI： 10.1007/s00224-008-9149-3

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

For a graph G, a detachment operation at a vertex transforms the graph into a new graph by splitting the vertex into several vertices in such a way that the original graph can be obtained by contracting all the split vertices into a single vertex. A graph obtained from a given graph G by applying detachment operations at several vertices is called a detachment of graph G. While detachment operations may decrease the connectivity of graphs, there are several works on conditions for preserving the connectivity. In this paper, we present necessary and sufficient conditions for a given graph/digraph to have an Eulerian detachment that satisfies a given local edge-connectivity requirement. We also discuss conditions for the detachment to be loopless. (C) 2008 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2008.08.001

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-642-10631-6_8

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

In an undirected graph G = (V, E) with a weight function w : E x V -> Q(+), the weighted degree d(w) (v; E) of a vertex v is defined as Sigma{w(e,v) | e is an element of E incident with v}. In this paper, we consider a network design problem which has upper-bounds on weighted degrees of vertices as its constraints while the objective is to compute a minimum cost graph with a prescribed connectivity. We propose bi-criteria approximation algorithms based on the iterative rounding, which has been successfully applied to the degree-bounded network design problem. A problem minimizing the maximum weighted degree of vertices is also discussed.

DOI： 10.1007/978-3-642-00202-1_19

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

In an undirected or directed graph, the edge-connectivity between two disjoint vertex sets X and Y. is defined as the minimum number of edges or arcs that should be removed for disconnecting all vertices in Y from those in X. In this paper, we discuss several conditions for a given undirected graph to have an orientation meeting the edge-connectivity requirements defined on some pairs of vertex sets.

DOI： 10.1007/978-3-642-10631-6_28

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

In this paper, we discuss the approximability of the capacitated b-edge dominating set problem, which generalizes the edge dominating set problem by introducing capacities and demands on the edges. We present an approximation algorithm for this problem and show that it achieves a factor of 8/3 for general graphs and a factor of 2 for bipartite graphs. Moreover, we discuss the relationships of the edge dominating set problem and the vertex cover problem. The results show that improving the approximation factor beyond 8/3 using our approach of adding valid inequalities to a natural linear programming relaxation is as hard as improving the approximation factor for vertex cover beyond 2. (c) 2007 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2007.06.009

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Given an edge-weighted graph, the induced matching problem is an edge packing problem, which asks to find a maximum weight edge set such that every edge in the graph is adjacent to at most one edge in the set. In this paper, we generalize this problem by introducing edge capacities and propose an approximation algorithm to the problem. The analysis of this algorithm is based on a relationship between two polytopes for an LP relaxation of the above problem and the capacitated b-matching problem. (c) 2006 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disopt.2006.11.004

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

We consider a problem for constructing a minimum cost r-edge-connected multigraph in which degree d(v) of each vertex v is an element of V is specified. In this paper, we propose a 3-approximation algorithm for this problem under the assumption that edge cost is metric, r(u, v) is an element of {1, 2} for each u, v is an element of V, and d(v) >= 2 for each v is an element of V. This problem is a generalization of metric TSP. We also propose an approximation algorithm for the digraph version of the problem.

DOI： 10.1093/ietisy/e90-d.2.432

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.15807/jorsj.50.339

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-540-72792-7_36

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-540-77050-3_7

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer k >= 1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex v G V is equal to b(v). This problem generalizes metric TSP. In this paper, we propose that the problem admits a p-approximation algorithm if b(v) ! 2, v G V, where rho = 2.5 if k is even, and p = 2.5 + 1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.

DOI： 10.1007/11970125_15

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：C R L PUBLISHING LTD  

Support vector machines (SVMs), especially nonlinear SVMs, are known to have high performance as classifiers of data. In this paper, we propose to construct a nonlinear SVM from a set of available prior knowledge on the problem domain and to determine their weights by using training data set, which we call the knowledge based SVM (KSVM). A basic tool for KSVM is the reduced SVM (RSVM) proposed by Y. -J. Lee and O. L. Mangasarian, in which kernel functions represent such knowledge. A KSVM has an advantage that its behavior is highly understandable as we can see how the kernels representing prior knowledge are combined into a classifier. It is confirmed by computational experiments that KSVMs can have high performance. We also discuss the separability condition and the VC dimension of KSVM.

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER-VERLAG BERLIN  

The edge dominating set problem is one of the fundamental covering problems in the field of combinatorial optimization. In this paper, we consider the b-edge dominating set problem, a generalized version of the edge dominating set problem. In this version, we are given a simple undirected graph G = (V, E) and a demand vector is an element of Z(E)(+). A set F of edges in G is called a b-edge dominating set if each edge e is an element of E is adjacent to at least b(e) edges in F, where we allow F to contain multiple copies of edges in E. Given a cost vector W is an element of Q(+)(E), the problem asks to find a minimum cost of a b-edge dominating set. We first show that there is a 8/3-approximation algorithm for this problem. We then consider approximation algorithms for other related problems.

DOI： 10.1007/11533719_76

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Poster presentation  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Poster presentation  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (invited, special)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Poster presentation  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (invited, special)  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (invited, special)  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap