Mechanism Design for Zero-Cost Bridge Online Segment with One-Direction Agents Uniform Distribution and Online Single Bin Packing Problem with Predictions

We investigate a variation of facility location problems (FLPs) that seeks to enhance agents’ access to a facility within the framework of mechanism design without monetary incentives. In this variation, agents express preferences for ideal facility locations along a real line segment, and all the agents are uniformly located at the same direction as the facility, but due to constraints such as limited space or construction costs, the facility's location is predetermined and cannot be moved. To improve agents’ accessibility, existing FLP literature in mechanism design suggests either structurally modifying the real line (e.g., by adding a new segment) or offering bridge services when structural modifications are not feasible. This paper concentrates on the latter approach, proposing the creation of an accessibility range to extend the facility's reach. Consequently, each agent's cost is determined by the distance from their ideal location to the facility, potentially through the bridge. We aim to design strategy proof mechanisms that accurately capture agents’ true ideal locations and construct accessibility bridge to approximately minimize either the social cost or the maximum cost for the agents. For both cost types, we develop strategy proof mechanisms with asymptotically tight approximation ratio bounds, i.e., 1.5. Also, we studied the approximation algorithm with tight upper bound and lower bound for online single bin packing problem with predictions. Bin packing problem is a famous problem in computer science and optimization areas. In this setting, there are some bins and items. Each item has its weight (size) and value. The model we discuss is that all the items have the same value as the weight. We prove that the upper bound and lower bound of this setting are both 2, which is tight.