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 条
  • [1] Approximate composable truthful mechanism design
    Ye, Deshi
    Zhang, Guochuan
    THEORETICAL COMPUTER SCIENCE, 2016, 654 : 188 - 198
  • [2] On the Two-Dimensional Knapsack Problem for Convex Polygons
    Merino, Arturo
    Wiese, Andreas
    ACM TRANSACTIONS ON ALGORITHMS, 2024, 20 (02)
  • [3] Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types
    Hoeksma, Ruben
    Uetz, Marc
    OPERATIONS RESEARCH, 2016, 64 (06) : 1438 - 1450
  • [4] Two-Dimensional Knapsack for Circles
    Lintzmayer, Carla Negri
    Miyazawa, Flavio Keidi
    Xavier, Eduardo Candido
    LATIN 2018: THEORETICAL INFORMATICS, 2018, 10807 : 741 - 754
  • [5] There is no EPTAS for two-dimensional knapsack
    Kulik, Ariel
    Shachnai, Hadas
    INFORMATION PROCESSING LETTERS, 2010, 110 (16) : 707 - 710
  • [6] Improved approximation for two-dimensional vector multiple knapsack
    Cohen, Tomer
    Kulik, Ariel
    Shachnai, Hadas
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2025, 124-125
  • [7] Truthful Mechanism Design for Multi-Dimensional Scheduling via Cycle Monotonicity
    Lavi, Ron
    Swamy, Chaitanya
    EC'07: PROCEEDINGS OF THE EIGHTH ANNUAL CONFERENCE ON ELECTRONIC COMMERCE, 2007, : 252 - 261
  • [8] A NOTE ON A TWO DIMENSIONAL KNAPSACK PROBLEM WITH UNLOADING CONSTRAINTS
    Moises da Silveira, Jefferson Luiz
    Xavier, Eduardo Candido
    Miyazawa, Flavio Keidi
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2013, 47 (04): : 315 - 324
  • [9] No truthful mechanism can be better than n approximate for two natural problems
    Leucci, Stefano
    Mamageishvili, Akaki
    Penna, Paolo
    GAMES AND ECONOMIC BEHAVIOR, 2018, 111 : 64 - 74
  • [10] Solving the Two-Dimensional Knapsack Problem Considering Cutting-Time and Emission of Particulate Matter in the Metalworking Industry
    Velasco-Carvajal, P.
    Camacho, G.
    Cuellar-Usaquen, D.
    Alvarez-Martinez, D.
    IEEE LATIN AMERICA TRANSACTIONS, 2018, 16 (12) : 2888 - 2895
12345