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 条

[31] Application of the method of approximate inverse to a two-dimensional inverse scattering problem
Abdullah, H
ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND MECHANIK, 2000, 80 : S815 - S816
[32] Spreadsheet solution of a two-dimensional Stefan problem using an approximate method
Kharab, A
HEAT TRANSFER ENGINEERING, 2000, 21 (05) : 65 - 71
[33] An approximate algorithm for the two-dimensional air cargo revenue management problem
Huang, Kuancheng
Chang, Ko-chen
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2010, 46 (03) : 426 - 435
[34] A Hybrid Demon Algorithm for the Two-Dimensional Orthogonal Strip Packing Problem
Chen, Bili
Wang, Yong
Yang, Shuangyuan
MATHEMATICAL PROBLEMS IN ENGINEERING, 2015, 2015
[35] An Exact Algorithm for the Two-Dimensional Orthogonal Packing Problem with Unloading Constraints
Cote, Jean-Francois
Gendreau, Michel
Potvin, Jean-Yves
OPERATIONS RESEARCH, 2014, 62 (05) : 1126 - 1141
[36] An optimal design problem for a two-dimensional flow in a duct
Wu, X
Cliff, EM
Gunzburger, MD
OPTIMAL CONTROL APPLICATIONS & METHODS, 1996, 17 (05): : 329 - 339
[37] 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
[38] Improved approximation for two-dimensional vector multiple knapsack
Cohen, Tomer
Kulik, Ariel
Shachnai, Hadas
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2025, 124-125
[39] Two-dimensional approximate wave function for the three-body Coulomb problem
Otranto, S
Cravero, WR
Gasaneo, G
Colavecchia, FD
Garibotti, CR
PHYSICAL REVIEW A, 2000, 61 (05): : 4
[40] APPROXIMATE SOLUTION OF THE TRUST REGION PROBLEM BY MINIMIZATION OVER TWO-DIMENSIONAL SUBSPACES
BYRD, RH
SCHNABEL, RB
SHULTZ, GA
MATHEMATICAL PROGRAMMING, 1988, 40 (03) : 247 - 263

← 1 2 3 4 5 →