4 results
Now showing1 - 4 of 4
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Envy-free dynamic pricing schemes(Informs, 2025-01-21); ; ; In combinatorial markets, the goal is typically to determine a pair of pricing and allocation of items that results in an efficient distribution of resources or maximizes the seller’s profit. In dynamic pricing schemes, agents arrive in an unspecified sequential order, and the prices can be updated between agent arrivals, which makes the concept of fairness of dynamic prices highly nontrivial. In markets with expected price deflation, a typical agent follows the prices prior to their purchase and become price insensitive after, whereas the opposite happens in markets with expected price inflation. To properly address these differences, we study the existence of optimal dynamic prices under fairness constraints in unit-demand markets. We propose five possible notions of envy freeness, depending on the period over which agents compare themselves to others: the entire time horizon, only the past, only the future, a mixture of the two, or only the present. For social welfare maximization, we give polynomial-time algorithms that always find envy-free optimal dynamic prices. For revenue maximization, we show that the corresponding problems are APX-hard if the ordering of the agents is fixed but are tractable when the seller can choose the ordering.Publicationtype: Journal Article51 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Approximations for many-visits multiple traveling salesman problemsA fundamental variant of the classical traveling salesman problem (TSP) is the so-called multiple TSP (mTSP), where a set of m salesmen jointly visit all cities from a set of n cities. The mTSP models many important real-life applications, in particular for vehicle routing problems. An extensive survey by Bektas (Omega 34(3), 2006) lists a variety of heuristic and exact solution procedures for the mTSP, which quickly solve particular problem instances. In this work we consider a further generalization of mTSP, the many-visits mTSP, where each city v has a request r(v) of how many times it should be visited by the salesmen. This problem opens up new real-life applications such as aircraft sequencing, while at the same time it poses several computational challenges. We provide multiple efficient approximation algorithms for important variants of the many-visits mTSP, which are guaranteed to quickly compute high-quality solutions for all problem instances.Publicationtype: Journal ArticleScopus© Citations 2 118 395 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , A 3/2-approximation for the metric many-visits path TSP(Society for Industrial and Applied Mathematics (SIAM), 2022); ; In the Many-visits Path TSP, we are given a set of n cities along with their pairwise distances (or cost) c(uv), and moreover each city v comes with an associated positive integer request r(v). The goal is to find a minimum-cost path, starting at city s and ending at city t, that visits each city v exactly r(v) times. We present a 3/2-approximation algorithm for the metric Many-visits Path TSP, that runs in time polynomial in n and poly-logarithmic in the requests r(v). Our algorithm can be seen as a far-reaching generalization of the 3/2-approximation algorithm for Path TSP by Zenklusen (SODA 2019), which answered a long-standing open problem by providing an efficient algorithm which matches the approximation guarantee of Christofides' algorithm from 1976 for metric TSP. One of the key components of our approach is a polynomial-time algorithm to compute a connected, degree bounded multigraph of minimum cost. We tackle this problem by generalizing a fundamental result of Király, Lau and Singh (Combinatorica, 2012) on the Minimum Bounded Degree Matroid Basis problem, and devise such an algorithm for general polymatroids, even allowing element multiplicities. Our result directly yields a 3/2-approximation to the metric Many-visits TSP, as well as a 3/2-approximation for the problem of scheduling classes of jobs with sequence-dependent setup times on a single machine so as to minimize the makespan.Publicationtype: Journal ArticleScopus© Citations 2 251 186 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Scheduling with non-renewable resources: Minimizing the sum of completion timesWe consider single-machine scheduling problems with a non-renewable resource. In this setting, there are n jobs, each characterized by a processing time, a weight, and a resource requirement. At given points in time, certain amounts of the resource are made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that each job has the required resource amount available at the start of its processing. We consider the objective of minimizing the weighted sum of completion times. The main contribution of the paper is a PTAS for the case of 0 processing times (formula presented). In addition, we show strong NP-hardness of the case of unit resource requirements and weights (formula presented), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the latter problem.Publicationtype: Conference Paper222