Search Results 1-20 of 950

  • Hardness of Instance Generation with Optimal Solutions for the Stable Marriage Problem

    Yuki Matsuyama , Shuichi Miyazaki

    … There are a lot of experimental studies for evaluating the performance of approximation algorithms or heuristics, using randomly generated or artificial instances. … There are a lot of experimental studies for evaluating the performance of approximation algorithms or heuristics, using randomly generated or artificial instances. …

    情報処理学会論文誌 62(2), 2021-02-15

    IPSJ 

  • Asymptotic Approximation Ratios for Certain Classes of Online Bin Packing Algorithms

    FUJIWARA Hiroshi , WANIKAWA Yuta , YAMAMOTO Hiroaki

    … <p>The performance of online algorithms for the bin packing problem is usually measured by the asymptotic approximation ratio. … However, even if an online algorithm is explicitly described, it is in general difficult to obtain the exact value of the asymptotic approximation ratio. … In this paper we show a theorem that gives the exact value of the asymptotic approximation ratio in a closed form when the item sizes and the online algorithm satisfy some conditions. …

    IEICE Transactions on Information and Systems E104.D(3), 362-369, 2021

    J-STAGE 

  • Hardness of Instance Generation with Optimal Solutions for the Stable Marriage Problem

    Matsuyama Yuki , Miyazaki Shuichi

    … There are a lot of experimental studies for evaluating the performance of approximation algorithms or heuristics, using randomly generated or artificial instances. …

    Journal of Information Processing 29(0), 166-173, 2021

    J-STAGE 

  • A Decomposition-Based Multi-Modal Multi-Objective Evolutionary Algorithm Transforming to Two-Objective Problems

    FUJII Yuto , MASUYAMA Naoki , NOJIMA Yusuke , ISHIBUCHI Hisao

    <p>パレートフロント上の1点に対応する解が複数存在する問題として，マルチモーダル多目的最適化問題がある．進化型マルチモーダル多目的最適化アルゴリズムでは，パレートフロントとパレートセットへの高い近似性能の両立が求められる．しかし，多くのアルゴリズムはパレートフロントへの収束性を優先的に考慮しているため，パレートフロントへの近似性能に比べてパレートセットへの近似性能が低くなる．本研究で …

    Journal of Japan Society for Fuzzy Theory and Intelligent Informatics 33(1), 537-542, 2021

    J-STAGE 

  • APPROXIMATION ALGORITHMS FOR A GENERALIZATION OF THE MAXIMUM BUDGET ALLOCATION

    Fukunaga Takuro

    … In this study, we consider a generalization of the MBA problem in which each item has a capacity constraint, and present two approximation algorithms for it. … The other is a pseudo-polynomial algorithm with approximation ratio 1/3·(1−r/4) that always outputs a feasible allocation.</p> …

    Journal of the Operations Research Society of Japan 64(1), 31-44, 2021

    J-STAGE 

  • Resilient Scheduling Heuristics for Rigid Parallel Jobs

    Benoit Anne , Fèvre Valentin Le , Raghavan Padma , Robert Yves , Sun Hongyang

    … This work generalizes the classical framework where jobs are known offline and do not fail: in this framework, list scheduling that gives priority to the longest jobs is known to be a 3-approximation when imposing to use shelves, and a 2-approximation without this restriction. … We show that when jobs can fail, using shelves can be arbitrarily bad, but unrestricted list scheduling remains a 2-approximation. …

    International Journal of Networking and Computing 11(1), 2-26, 2021

    J-STAGE 

  • Hardness of Instance Generation with Optimal Solutions for the Stable Marriage Problem

    Matsuyama Yuki , Miyazaki Shuichi

    … There are a lot of experimental studies for evaluating the performance of approximation algorithms or heuristics, using randomly generated or artificial instances. …

    Journal of Information Processing (29), 166-173, 2021

    IR 

  • Branching Deep Q-network Agent with Reward Allocation Mechanism for Joint Replenishment Policy  [in Japanese]

    Hiroshi Suetsugu , Yoshiaki Narusue , Hiroyuki Morikawa

    … By proposing a Q-learning agent with function approximation, called the branching deep Q-network (DQN) with reward allocation, the purpose of this paper is to ease the strict assumptions, such as the zero lead time or the stationary demand, which are essential in the existing heuristic algorithms. …

    情報処理学会論文誌数理モデル化と応用（TOM） 13(2), 36-49, 2020-08-28

    IPSJ 

  • Two approximation algorithms for probabilistic coalition structure generation with quality bound

    Matsumura Kouki , Kodric Bojana , Okimoto Tenda , Hirayama Katsutoshi

    … In PCSG, since finding the optimal coalition structure easily becomes intractable, it is important to consider approximation algorithms, i.e., to consider a trade-off between the quality of the returned solution and tractability. … Approximation algorithms for PCSG called Bounded Approximation Algorithm based on Attendance Types (BAAAT) and Involved BAAAT (IBAAAT) are then presented. …

    Autonomous Agents and Multi-Agent Systems 34(1), 25, 2020-02-18

    IR 

  • Probablistic Methods for Higher-order Weak Approximation of Stochastic Differential Equations  [in Japanese]

    Ninomiya Syoiti

    … is a diffusion process defined by a stochastic differential equation (SDE) is called weak approximation of the SDE. … The author discusses higherorder discretization algorithms based on Kusuokaʼs theory. … The fundamental theorem by Kusuoka and three algorithms are explained.</p> …

    Bulletin of the Japan Society for Industrial and Applied Mathematics 30(4), 8-15, 2020

    J-STAGE 

  • Approximation Algorithms for the Maximum Path Cover Problem with Length Costs  [in Japanese]

    小林 賢也 , Lin Guohui , 宮野 英次 , 斎藤 寿樹 , 鈴木 顕 , 歌島 侃勇 , 八木田 剛

    <p>長さコスト付きパスカバー最大化問題と呼ばれるグラフ最適化問題を考える．本問題に対して4近似アルゴリズムを設計する．また，入力グラフの最大次数が3以下である場合には，2.5近似となること，タイトなグラフが存在することを示す．</p>

    Record of Joint Conference of Electrical and Electronics Engineers in Kyushu 2020(0), 318-318, 2020

    J-STAGE 

  • A Multi-modal Multi-objective Evolutionary Algorithm based on Transformation to Two-objective Optimization Problems  [in Japanese]

    Fujii Yuto , Masuyama Naoki , Nojima Yusuke , Ishibuchi Hisao

    <p> </p>

    Proceedings of the Fuzzy System Symposium 36(0), 53-58, 2020

    J-STAGE 

  • Simple Tuning and Low-Computational-Cost Controller for Enhancing Energy Efficiency of Autonomous-Driving Electric Vehicles

    Hattori Mitsuhiro , Fujimoto Hiroshi , Hori Yoichi , Takeda Yusuke , Sato Koji

    … <p>Previous studies have proposed various optimization algorithms, such as dynamic programming (DP) and model predictive control (MPC), to reduce the energy consumption of autonomous-driving vehicles. … The effect of changing this parameter, the solver of the LQR for the LPV model, and the influence of the approximation of the models were analyzed. …

    IEEJ Journal of Industry Applications 9(4), 358-365, 2020

    J-STAGE 

  • Function approximation of Cognitive Satisficing Value Function  [in Japanese]

    YOSHII Yuki , KONO Yu , TAKAHASHI Tatsuji

    <p>人間にはある目的基準を超える収益が得られる手順を発見するとそれに満足し，探索を打ち切るといった満足化と呼ばれる意思決定傾向が存在する．この傾向を強化学習に応用したのが Risk-sensitive Satisficing (RS) である．深層強化学習は人間が行うようなレトロゲームのプレイや運動制御などへ強化学習の適用範囲を広げた．しかし，情報を自ら探索しなければならない点は変わ …

    Proceedings of the Annual Conference of JSAI JSAI2020(0), 2I5GS202-2I5GS202, 2020

    J-STAGE 

  • IMPROVING APPROXIMATION RATIOS FOR THE CLUSTERED TRAVELING SALESMAN PROBLEM

    Kawasaki Masamune , Takazawa Kenjiro

    … (2000) designed approximation algorithms for several variants of CTSP by decomposing it into subproblems including the traveling salesman path problem (TSPP). … In this paper, we improve approximation ratios by applying a recent improved approximation algorithm for TSPP by Zenklusen (2019).</p> …

    Journal of the Operations Research Society of Japan 63(2), 60-70, 2020

    J-STAGE 

  • AN EFFICIENT BRANCH-AND-CUT ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION

    Uematsu Naoya , Umetani Shunji , Kawahara Yoshinobu

    … Although a variety of greedy algorithms quickly find good feasible solutions for many instances while guaranteeing (1−1/<i>e</i>)-approximation ratio, we still encounter many real applications that ask optimal or better solutions within reasonable computation time. … According to computational results for well-known benchmark instances, our algorithm achieves better performance than the state-of-the-art exact algorithms.</p> …

    Journal of the Operations Research Society of Japan 63(2), 41-59, 2020

    J-STAGE 

  • Binaural rendering technology over loudspeakers and headphones

    Yao Dingding , Xu Huaxing , Li Junfeng , Xia Risheng , Yan Yonghong

    … A stochastic robust approximation method is then suggested to further improve its robustness against the perturbation perception caused by the listener's head movement or rotation. … The effectiveness and performance of the suggested algorithms are verified by subjective and objective experiments.</p> …

    Acoustical Science and Technology 41(1), 134-141, 2020

    J-STAGE 

  • Approximation Algorithms for Minimum Cost Data Gathering Using Self-Coding  [in Japanese]

    中道 大貴 , 宮本 紘之 , 石井 多美雄 , 山田 敏規

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 119(314), 79-84, 2019-11-28

  • Approximation Algorithms for Minimum Cost Data Gathering Using Self-Coding  [in Japanese]

    中道 大貴 , 宮本 紘之 , 石井 多美雄 , 山田 敏規

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 119(313), 79-84, 2019-11-28

  • Experimental Evaluation of Approximation and Heuristic Algorithms for Maximum Distance-Bounded Subgraph Problems

    Asahiro Yuichi , Kubo Tomohiro , Miyano Eiji

    … in Optimal approximation algorithms for maximum distance-bounded subgraph problems. … As for approximability of Maxd-Clique and Maxd-Club, a polynomial-time algorithm, called ReFindStar d, that achieves an optimal approximation ratio of O(n1/2) for Maxd-Clique and Maxd-Club was designed for any integer d≥2 in Asahiro et al. … (2010, 2018) that although the approximation ratio of ByFindStar d is much worse for any odd d≥3, its time complexity is better than ReFindStar d. …

    The Review of Socionetwork Strategies 13(2), 143-161, 2019-04-16

    IR 

Page Top