Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem

被引：1
作者：
Ye, Deshi [1 ]
Zhang, Guochuan [1 ]
机构：
[1] Zhejiang Univ, Coll Comp Sci, Hangzhou 310027, Zhejiang, Peoples R China
来源：
COMPUTING AND COMBINATORICS | 2015年 / 9198卷
关键词：
Mechanism design; Knapsack auction; Approximation algorithms; ALGORITHMS; RECTANGLES;
D O I：
10.1007/978-3-319-21398-9_31
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper provides a technique for designing truthful mechanisms for a combinatorial optimization problem, which requires composition algorithms. We show that the composition algorithm A o B is monotone if the algorithm A and the algorithm B are both monotone. Then, we apply this technique to the two-dimensional orthogonal knapsack problem with provable approximation bounds, improving the previous results in [5].
引用
收藏
页码：390 / 401
页数：12
相关论文
共 50 条
  • [21] An approximation solution for the 2-median problem on two-dimensional meshes
    Tse, SSH
    Lau, FCM
    AINA 2005: 19th International Conference on Advanced Information Networking and Applications, Vol 2, 2005, : 457 - 460
  • [22] The phase problem for two-dimensional crystals. II. Simulations
    Arnal, Romain D.
    Zhao, Yun
    Mitra, Alok K.
    Spence, John C. H.
    Millane, Rick P.
    ACTA CRYSTALLOGRAPHICA A-FOUNDATION AND ADVANCES, 2018, 74 : 537 - 544
  • [23] Corner occupying theorem for the two-dimensional integral rectangle packing problem
    Huang WenQi
    Ye Tao
    Chen DuanBing
    SCIENCE CHINA-INFORMATION SCIENCES, 2012, 55 (11) : 2466 - 2472
  • [24] Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem
    Boschetti, Marco A.
    Maniezzo, Vittorio
    Strappaveccia, Francesco
    INFORMS JOURNAL ON COMPUTING, 2016, 28 (03) : 540 - 552
  • [25] The two-dimensional cutting stock problem with usable leftovers and uncertainty in demand
    Nascimento, Douglas Nogueira
    Cherri, Adriana Cristina
    Oliveira, Jose Fernando
    COMPUTERS & INDUSTRIAL ENGINEERING, 2023, 186
  • [26] Models for the two-dimensional two-stage cutting stock problem with multiple stock size
    Furini, Fabio
    Malaguti, Enrico
    COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (08) : 1953 - 1962
  • [27] An agent-based approach to the two-dimensional guillotine bin packing problem
    Polyakovsky, Sergey
    M'Hallah, Rym
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 192 (03) : 767 - 781
  • [28] Aggregated state dynamic programming for a multiobjective two-dimensional bin packing problem
    Liu, Ya
    Chu, Chengbin
    Yu, Yugang
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2012, 50 (15) : 4316 - 4325
  • [29] EPSO for Solving Non-oriented Two-dimensional Bin Packing Problem
    Omar, Mohamed K.
    Ramakrishnan, Kumaran
    2011 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM), 2011, : 106 - 110
  • [30] Heuristic for the two-dimensional arbitrary stock-size cutting stock problem
    Cui, Yaodong
    Cui, Yi-Ping
    Yang, Liu
    COMPUTERS & INDUSTRIAL ENGINEERING, 2014, 78 : 195 - 204
12345