Traditionally, the problem of apportioning the seats of a legislative body has been viewed as a oneshot process with no dynamic considerations. While this approach is reasonable for some instances of the problem, dynamic aspects play an important role in many others. In this paper, we initiate the study of apportionment problems in an online setting. Specifically, we introduce an online algorithmic framework to handle proportional apportionment with no information about future events. In this model, time is discrete and there are \(n\) parties that receive a certain share of the votes at each time step. An online algorithm needs to irrevocably assign a prescribed number of seats at each time, ensuring that each party receives its fractional share rounded up or down, and that the cumulative number of seats allocated to each party remains close to its cumulative share up to that time.

We study a variant of the prophet inequality with limited information, where the decision maker has access only to the first k moments of each random variable, rather than their full distributions. In this work, we show that even with full moment knowledge (i.e., k=∞), the best possible competitive ratio is Θ(1/ logn), and that this can already be achieved with only knowledge of the first moment. While the lower bound is simple and is attained by a standard exponential bucketing algorithm, the upper bound requires a subtle construction. This involves using Vandermonde matrices first to construct a parametrized family of distributions for which the first k moments coincide, and for which the expected maximum of n such copies varies widely across different parameter choices. Using Prokhorov’s theorem, we establish the existence of limit distributions, which we show have all their moments equal. Finally, we describe a construction where an adversary can select equally looking instances combining these distributions, making it impossible for the decision maker to obtain a factor better than O(1/ logn) of the expected maximum.

A classic statistical problem is to study the asymptotic behavior of the order statistics of a large number of independent samples taken from a distribution with finite expectation. This behavior has implications for several core problems in machine learning and economics—including robust learning under adversarial noise, best-arm identification in bandit algorithms, revenue estimation in second- price auctions, and the analysis of tail-sensitive statistics used in out-of-distribution detection. The research question we tackle in this paper is: How large can the expectation of the $\ell$-th maximum of the $n$ samples be? For $\ell=1$, i.e., the maximum, this expectation is known to grow as $o(n)$, which can be shown to be tight. We show that there is a sharp contrast when considering any fixed $\ell>1$. Surprisingly, in this case, the largest possible growth rate for all fixed $\ell>1$ is $O(\frac{n}{\log(n)\log\log(n)})$ and $\Omega(\frac{n}{\log(n)(\log\log(n))^{1.01}})$. Our result is actually finer than the latter and provides a sharp characterization of the largest achievable growth rate for the expectation of the $\ell$-th maximum of $n$ i.i.d. samples. Beyond the theoretical analysis, we support our findings with extensive simulations. These empirical results highlight a notable phenomenon: although the multiplicative gap between the maximum and the second maximum grows quickly with $n$, the ratio remains approximately constant in 99\% of trials. This suggests that while worst-case growth is sharp and meaningful, typical-case behavior may be significantly more stable.

A typical goal for a gambler facing an online selection problem is to choose the best element, particularly in comparison to the best hindsight-optimal selection. This objective is nontrivial when there is high competition for top elements. For example, highly skilled job candidates are often recruited by top companies, leaving less competitive companies with the remaining candidates. This phenomenon introduces nontrivial correlations among the remaining candidates; hence, a gambler facing this problem with misaligned beliefs might act sub optimally if she expects a top element to still be available for selection. Motivated by these considerations, we introduce the residual prophet inequality (k-RPI) problem. In the k-RPI problem, we consider a finite sequence of n nonnegative independent random values with known distributions and a known integer 0 ≤ k ≤ n - 1. Before the gambler observes the sequence, the top k values are removed from the sequence whereas the remaining n - k values are streamed sequentially to the gambler. Upon observing a value, the gambler must decide irrevocably if to accept/reject a value without the possibility of revisiting past values. We study two variants of k-RPI, according to whether the gambler learns online of the identity of the variable that he sees (FI-model) or not (NI-model). Our main result is a randomized algorithm in the FI-model with competitive ratio of at least 1/(k + 2), which we show is tight. Our algorithm is data-driven and requires access only to the k + 1 largest values of a single sample from the n input distributions. In the NI-model, we provide a similar algorithm that guarantees a competitive ratio of 1/(2k + 2). We further analyze independent and identically distributed instances when k = 1. We build a single-threshold algorithm with a competitive ratio of at least 0.4901, and show that no single-threshold strategy can get a competitive ratio greater than 0.5464.

The apportionment problem constitutes a fundamental problem in democratic societies: How to distribute a fixed number of seats among a set of states in proportion to the states’ populations? This—seemingly simple—task has led to a rich literature and has become well known in the context of the US House of Representatives. In this paper, we connect the design of monotone apportionment methods to classic problems from discrete geometry and combinatorial optimization and explore the extent to which randomization can enhance proportionality.

Apportionment is the act of distributing the seats of a legislature among political parties (or states) in proportion to their vote shares (or populations). A famous impossibility by Balinski and Young (2001) shows that no apportionment method can be proportional up to one seat (quota) while also responding monotonically to changes in the votes (population monotonicity). Grimmett (2004) proposed to overcome this impossibility by randomizing the apportionment, which can achieve quota as well as perfect proportionality and monotonicity --- at least in terms of the expected number of seats awarded to each party. Still, the correlations between the seats awarded to different parties may exhibit bizarre non-monotonicities. When parties or voters care about joint events, such as whether a coalition of parties reaches a majority, these non-monotonicities can cause paradoxes, including incentives for strategic voting.

We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the (1 - ε)-competition complexity of different types of online algorithms. This metric asks for the smallest k such that the expected value of the online algorithm on k copies of the original instance, is at least a (1 - ε)-approximation to the expected offline optimum on a single copy.

We study a market game with n ≥ 2 players competing over m ≥ 1 divisible resources of different finite capacities. Resources are traded via the proportional sharing mechanism, where players are price-anticipating, meaning that they can influence the prices with their bids. Additionally, each player has an initial endowment of the resources which are sold at market prices. Although the players’ total profit functions may be discontinuous in the bids, we prove existence and uniqueness of pure Nash equilibria of the resulting market game. Then, we study a discrete dynamic arising from repeatedly taking the (unique) equilibrium resource allocation as initial endowments for the next market game. We prove that the total utility value of the dynamic converges to either an optimal allocation value (maximizing total utility over the allocation space) or to a restricted optimal allocation value, where the restriction is defined by fixing some tight resources which are exclusively allocated to a single player. As a corollary, it follows that for strictly concave utility functions, the aggregated allocation vector of the dynamic converges to the unique (possibly restricted) optimal aggregated allocation, and for linear utility functions, we even get convergence of the dynamic to a (possibly restricted) optimal solution in the (non-aggregated) original allocation space.

In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm observes a sequence of prices one after the other. At each time step, the online algorithm can decide to buy and pay the current price if it does not hold the item already; or it can decide to sell and collect the current price as a reward if it holds the item.

In online combinatorial auctions m indivisible items are to be allocated to n agents who arrive online. Agents have random valuations for the different subsets of items and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. The study of prophet inequalities for online combinatorial auctions has been an intensive area of research in recent years, and constant factor prophet inequalities are known when the agents’ valuation functions are submodular or fractionally subadditive. Despite many efforts, for the more general case of subadditive valuations, the best known prophet inequality has an approximation guarantee of O(loglogm). In this paper, we prove the existence of a constant factor prophet inequality for the subadditive case, resolving a central open problem in the area.

We study the competition complexity of dynamic pricing relative to the optimal auction in the fundamental single-item setting. In prophet inequality terminology, we compare the expected reward Am(F) achievable by the optimal online policy on m i.i.d. random variables drawn from F to the expected maximum Mn(F) of n i.i.d. draws from the same distribution. We ask how big does m have to be to ensure that (1+ε) Am(F) ≥ Mn(F) for all F.

The secretary problem or game of Googol are classic models for online selection problems. In this paper we consider a variant of the problem and explore its connections to data-driven online selection. Specifically, we are given $n$ cards with arbitrary non-negative numbers written on both sides. The cards are randomly placed on $n$ consecutive positions on a table, and for each card, the visible side is also selected at random. The player sees the visible side of all cards and wants to select the card with the maximum hidden value. To this end, the player flips the first card, sees its hidden value and decides whether to pick it or drop it and continue with the next card. We study algorithms for two natural objectives: maximizing the probability of selecting the maximum hidden value, and maximizing the expectation of the selected hidden value. For the former objective we obtain a simple $0.45292$-competitive algorithm. For the latter, we obtain a $0.63518$-competitive algorithm. Our main contribution is to set up a model allowing to transform probabilistic optimal stopping problems into purely combinatorial ones. For instance, we can apply our results to obtain lower bounds for the single sample prophet secretary problem.

There is growing awareness and concern about fairness in machine learning and algorithm design. This is particularly true in online selection problems where decisions are often biased, for example, when assessing credit risks or hiring staff. We address the issues of fairness and bias in online selection by introducing multi-color versions of the classic secretary and prophet problem. Interestingly, existing algorithms for these problems are either very unfair or very inefficient, so we develop optimal fair algorithms for these new problems and provide tight bounds on their competitiveness. We validate our theoretical findings on real-world data.

A prophet inequality states, for some $α\in[0,1]$, that the expected value achievable by a gambler who sequentially observes random variables $X_1,\dots,X_n$ and selects one of them is at least an $α$ fraction of the maximum value in the sequence. We obtain three distinct improvements for a setting that was first studied by Correa et al. (EC, 2019) and is particularly relevant to modern applications in algorithmic pricing. In this setting, the random variables are i.i.d. from an unknown distribution and the gambler has access to an additional $βn$ samples for some $β\geq 0$. We first give improved lower bounds on $α$ for a wide range of values of $β$; specifically, $α\geq(1+β)/e$ when $β\leq 1/(e-1)$, which is tight, and $α\geq 0.648$ when $β=1$, which improves on a bound of around $0.635$ due to Correa et al. (SODA, 2020). Adding to their practical appeal, specifically in the context of algorithmic pricing, we then show that the new bounds can be obtained even in a streaming model of computation and thus in situations where the use of relevant data is complicated by the sheer amount of data available. We finally establish that the upper bound of $1/e$ for the case without samples is robust to additional information about the distribution, and applies also to sequences of i.i.d. random variables whose distribution is itself drawn, according to a known distribution, from a finite set of known candidate distributions. This implies a tight prophet inequality for exchangeable sequences of random variables, answering a question of Hill and Kertz (Contemporary Mathematics, 1992), but leaves open the possibility of better guarantees when the number of candidate distributions is small, a setting we believe is of strong interest to applications.

Deciding how to allocate the seats of a house of representatives is one of the most fundamental problems in the political organization of societies, and has been widely studied over already two centuries. The idea of proportionality is at the core of most approaches to tackle this problem, and this notion is captured by the divisor methods, such as the Jefferson/D'Hondt method. In a seminal work, Balinski and Demange extended the single-dimensional idea of divisor methods to the setting in which the seat allocation is simultaneously determined by two dimensions, and proposed the so-called biproportional apportionment method. The method, currently used in several electoral systems, is however limited to two dimensions and the question of extending it is considered to be an important problem both theoretically and in practice. In this work we initiate the study of multidimensional proportional apportionment. We first formalize a notion of multidimensional proportionality that naturally extends that of Balinski and Demange. By means of analyzing an appropriate integer linear program we are able to prove that, in contrast to the two-dimensional case, the existence of multidimensional proportional apportionments is not guaranteed and deciding its existence is NP-complete. Interestingly, our main result asserts that it is possible to find approximate multidimensional proportional apportionments that deviate from the marginals by a small amount. The proof arises through the lens of discrepancy theory, mainly inspired by the celebrated Beck-Fiala Theorem. We finally evaluate our approach by using the data from the recent 2021 Chilean Constitutional Convention election.

In the secretary problem we are faced with an online sequence of elements with values. Upon seeing an element we have to make an irrevocable take-it-or-leave-it decision. The goal is to maximize the probability of picking the element of maximum value. The most classic version of the problem is that in which the elements arrive in random order and their values are arbitrary. Here, the optimal algorithm picks the maximum value with probability at least 1/e. However, by varying the available information, new interesting problems arise. For instance, in the full information variant of the secretary problem the values are i.i.d. samples from a known distribution. Naturally, the best possible success probability increases and turns out to be approximately 0.58. Also, the case in which the arrival order is adversarial instead of random leads to interesting variants that have been considered in the literature. In this paper we study both the random order and adversarial order secretary problems with an additional twist. The values are arbitrary, but before starting the online sequence we independently sample each element with a fixed probability p. The sampled elements become our information or history set and the game is played over the remaining elements. We call these problems the random order secretary problem with p-sampling (ROSp for short) and the adversarial order secretary problem with p-sampling (AOSp for short). Our main result is to obtain best possible algorithms for both problems and all values of p. As p grows to 1 the obtained guarantees converge to the optimal guarantees in the full information case. In the adversarial order setting, the best possible algorithm turns out to be a simple fixed threshold algorithm in which the optimal threshold is a function of p only. Therefore, even knowledge of the total number of elements is unnecessary. Proving that this algorithm is optimal involves a novel technique, which boils down to analyzing a related game in a conflict graph over binary sequences. In the random order setting we prove that the best possible algorithm is characterized by a fixed sequence of time thresholds, dictating at which point in time we should start accepting a value that is both a maximum of the online sequence and has a given ranking within the sampled elements. Surprisingly, this sequence of time thresholds arises from a separable and convex optimization problem whose solution is independent of p.

Research on dynamic pricing has been growing during the last four decades due to its use in practice by a variety of companies as well as the several model variants that can be considered. In this work, we consider the particular pricing problem where a firm wants to sell one item to a single buyer in order to maximize expected revenues. The firm commits to a price function over an infinite horizon. The buyer has a private value for the item and purchases at the time when his utility is maximized. In our model, the buyer is more impatient than the seller and we study how important is to observe the buyer time arrival in terms of the seller's expected revenue. When the seller can observe the arrival of the buyer, she can make the price function contingent on the buyer's arrival time. On the contrary, when the seller cannot observe the arrival, her price function is fixed at time zero for the whole horizon. The value of observabilityis defined as the worst case ratio between the expected revenue of the seller when she observes the buyer's arrival and that when she does not. Our main result is to prove that in a very general setting, the value of observability is at most~4.911. To obtain this result we fully characterize the observable setting and use this solution to construct a random and periodic price function for the unobservable case.

The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. In this paper we consider a variant of the problem and explore its connections to data-driven online selection. Specifically, we are given n cards with arbitrary nonnegative numbers written on both sides. The cards are randomly placed on n consecutive positions on a table, and for each card, the visible side is also selected at random. The player sees the visible side of all cards and wants to select the card with the maximum hidden value. To this end, the player flips the first card, sees its hidden value and decides whether to pick it or drop it and continue with the next card. We study algorithms for two natural objectives. In the first one, similar to the secretary problem, the player wants to maximize the probability of selecting the maximum hidden value. We show that this can be done with probability at least 0.45292. In the second objective, similar to the prophet inequality, the player wants to maximize the expectation of the selected hidden value. Here we show a guarantee of at least 0.63518 with respect to the expected maximum hidden value. Our algorithms result from combining three basic strategies. One is to stop whenever we see a value larger than the initial n visible numbers. The second one is to stop the first time the last flipped card's value is the largest of the currently n visible numbers in the table. And the third one is similar to the latter but to stop it additionally requires that the last flipped value is larger than the value on the other side of its card. We apply our results to the prophet secretary problem with unknown distributions, but with access to a single sample from each distribution. In particular, our guarantee improves upon 1 – 1/e for this problem, which is the currently best known guarantee and only works for the i.i.d. prophet inequality with samples.

In the classic prophet inequality, a problem in optimal stopping theory, samples from independent random variables (possibly differently distributed) arrive online. A gambler that knows the distributions, but cannot see the future, must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet, that sees all the realizations in advance, gets. In the late seventies, Krengel and Sucheston, and Garling [16], established that this worst case ratio is a constant and that 1/2 is the best possible such constant. In the last decade the theory of prophet inequalities has resurged as an important problem due to its connections to posted price mechanisms, frequently used in online sales. A particularly interesting variant is the so-called Prophet Secretary problem, in which the only difference is that the samples arrive in a uniformly random order. For this variant several algorithms are known to achieve a constant of 1 – 1/e and very recently this barrier was slightly improved by Azar et al. [3]. In this paper we derive a way of analyzing multithreshold strategies that basically sets a nonincreasing sequence of thresholds to be applied at different times. The gambler will thus stop the first time a sample surpasses the corresponding threshold. Specifically we consider a class of very robust strategies that we call blind quantile strategies. These constitute a clever generalization of single threshold strategies and consist in fixing a function which is used to define a sequence of thresholds once the instance is revealed. Our main result shows that these strategies can achieve a constant of 0.669 in the Prophet Secretary problem, improving upon the best known result of Azar et al. [3], and even that of Beyhaghi et al. [4] that works in the case the gambler can select the order of the samples. The crux of the analysis is a very precise analysis of the underlying stopping time distribution for the gambler's strategy that is inspired by the theory of Schur convex functions. We further prove that our family of blind strategies cannot lead to a constant better than 0.675. Finally we prove that no nonadaptive algorithm for the gambler can achieve a constant better than 0.732, which also improves upon a recent result of Azar et al. [3]. Here, a nonadaptive algorithm is an algorithm whose decision to stop can depend on the index of the random variable being sampled, on the value sampled, and on the time, but not on the history that has been observed.

Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: owners (operators) of the network and users of the network. Owners of the network post a price for usage of the link they own so as to attract users and maximize profit; users of the network select routes based on price and level of use by other users. We point out that an equilibrium in these games may not exist, may not be unique and may induce an arbitrarily inefficient network performance. Our main result is to observe that a simple regulation on the network owners market solves all three issues above. Specifically, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge, then: the game among the link operators has a unique and strong Nash equilibrium and the users' game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls. As a secondary objective, we want to compute great tolls that minimize total users' payments and we provide a linear program that does this. We obtain multiplicative approximation results compared to the optimal total users' payments for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity case we obtain a bound that only depends on the topology of the network. Lastly, we show how the same mechanism of setting appropriate caps on the allowable prices extends to the model of elastic demands.

Posted price mechanisms constitute a widely used way of selling items to strategic consumers. Although suboptimal, the attractiveness of these mechanisms comes from their simplicity and easy implementation. In this paper, we investigate the performance of posted price mechanisms when customers arrive in an unknown random order. We compare the expected revenue of these mechanisms to the expected revenue of the optimal auction in two different settings. Namely, the nonadaptive setting in which all offers are sent to the customers beforehand, and the adaptive setting in which an offer is made when a consumer arrives. For the nonadaptive case, we obtain a strategy achieving an expected revenue within at least a 1-1/e fraction of that of the optimal auction. We also show that this bound is tight, even if the customers have i.i.d. valuations for the item. For the adaptive case, we exhibit a posted price mechanism that achieves a factor 0.745 of the optimal revenue, when the customers have i.i.d. valuations for the item. Furthermore, we prove that our results extend to the prophet inequality setting and in particular our result for i.i.d. random valuations resolves a problem posed by Hill and Kertz. [13]

Imagine a wooden plate with a set of non-overlapping geometric objects painted on it. How many of them can a carpenter cut out using a panel saw making guillotine cuts, i.e., only moving forward through the material along a straight line until it is split into two pieces? Already fifteen years ago, Pach and Tardos investigated whether one can always cut out a constant fraction if all objects are axis-parallel rectangles. However, even for the case of axis-parallel squares this question is still open. In this paper, we answer the latter affirmatively. Our result is constructive and holds even in a more general setting where the squares have weights and the goal is to save as much weight as possible. We further show that when solving the more general question for rectangles affirmatively with only axis-parallel cuts, this would yield a combinatorial O(1)-approximation algorithm for the Maximum Independent Set of Rectangles problem, and would thus solve a long-standing open problem. In practical applications, like the mentioned carpentry and many other settings, we can usually place the items freely that we want to cut out, which gives rise to the two-dimensional guillotine knapsack problem: Given a collection of axis-parallel rectangles without presumed coordinates, our goal is to place as many of them as possible in a square-shaped knapsack respecting the constraint that the placed objects can be separated by a sequence of guillotine cuts. Our main result for this problem is a quasi-PTAS, assuming the input data to be quasi-polynomially bounded integers. This factor matches the best known (quasi-polynomial time) result for (non-guillotine) two-dimensional knapsack.

In the “The curse of simultaneity”, Paes Leme et al. show that there are interesting classes of games for which sequential decision making and corresponding subgame perfect equilibria avoid worst case Nash equilibria, resulting in substantial improvements for the price of anarchy. This is called the sequential price of anarchy. A handful of papers have lately analysed it for various problems, yet one of the most interesting open problems was to pin down its value for linear atomic routing (also: network congestion ) games, where the price of anarchy equals 5/2. The main contribution of this paper is the surprising result that the sequential price of anarchy is unbounded even for linear symmetric routing games, thereby showing that sequentiality can be arbitrarily worse than simultaneity for this class of games. Complementing this result we solve an open problem in the area by establishing that the (regular) price of anarchy for linear symmetric routing games equals 5/2. Additionally, we prove that in these games, even with two players, computing the outcome of a subgame perfect equilibrium is \(\mathsf {NP}\) -hard. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Motivated by the recent emergence of the so-called opportunistic communication networks, we consider the issue of adaptivity in the most basic continuous time (asynchronous) rumor spreading process. In our setting a rumor has to be spread to a population; the service provider can push it at any time to any node in the network and has unit cost for doing this. On the other hand, as usual in rumor spreading, nodes share the rumor upon meeting and this imposes no cost on the service provider. Rather than fixing a budget on the number of pushes, we consider the cost version of the problem with a fixed deadline and ask for a minimum cost strategy that spreads the rumor to every node. A non-adaptive strategy can only intervene at the beginning and at the end, while an adaptive strategy has full knowledge and intervention capabilities. Our main result is that in the homogeneous case (where every pair of nodes randomly meet at the same rate) the benefit of adaptivity is bounded by a constant. This requires a subtle analysis of the underlying random process that is of interest in its own right. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

After a sequence of improvements Boyd et al. [TSP on cubic and subcubic graphs, Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 6655, Springer, Heidelberg, 2011, pp. 65--77] proved that any 2-connected graph whose $n$ vertices have degree 3, i.e., a cubic 2-connected graph, has a Hamiltonian tour of length at most (4/3)n, establishing in particular that the integrality gap of the subtour LP is at most 4/3 for cubic 2-connected graphs and matching the conjectured value of the famous 4/3 conjecture. In this paper we improve upon this result by designing an algorithm that finds a tour of length (4/3-1/61236)n, implying that cubic 2-connected graphs are among the few interesting classes of graphs for which the integrality gap of the subtour LP is strictly less than 4/3. With the previous result, and by considering an even smaller $\epsilon$, we show that the integrality gap of the TSP relaxation is at most $4/3- \epsilon$ even if the graph is not 2-connected (i.e., for cubic connected graphs), implying that the approximability threshold of the TSP in cubic graphs is strictly below 4/3. Finally, using similar techniques we show, as an additional result, that every Barnette graph admits a tour of length at most (4/3 - 1/18)n.

We study coordination mechanisms aiming to minimize the weighted sum of completion times of jobs in the context of selfish scheduling problems. Our goal is to design local policies that achieve a good price of anarchy in the resulting equilibria for unrelated machine scheduling. To obtain these approximation bounds, we introduce a new technique that while conceptually simple, seems to be quite powerful. The method entails mapping strategy vectors into a carefully chosen inner product space; costs are shown to correspond to the norm in this space, and the Nash condition also has a simple description. With this structure in place, we are able to prove a number of results, as follows. First, we consider Smith's Rule, which orders the jobs on a machine in ascending processing time to weight ratio, and show that it achieves an approximation ratio of 4. We also demonstrate that this is the best possible for deterministic non-preemptive strongly local policies. Since Smith's Rule is always optimal for a given fixed assignment, this may seem unsurprising, but we then show that better approximation ratios can be obtained if either preemption or randomization is allowed.

We study a prize-collecting version of the uncapacitated facility location problem and of the p-median problem. We say that the uncapacitated facility location polytope has the intersection property if adding the extra equation that fixes the number of opened facilities does not create any fractional extreme point. We characterize the graphs for which this polytope has the intersection property and give a complete description of the polytope for this class of graphs. This characterization yields a polynomial time cutting plane algorithm for these graphs. We also give a combinatorial polynomial time algorithm to solve the different variants of the p-median and facility location problems studied in this paper.

We consider a generalization of edge coloring bipartite graphs in which every edge has a weight in $[0,1]$ and the coloring of the edges must satisfy that the sum of the weights of the edges incident to a vertex v of any color must be at most 1. For unit weights, König's theorem says that the number of colors needed is exactly the maximum degree. For this generalization, we show that $2.557 n + o(n)$ colors are sufficient, where n is the maximum total weight adjacent to any vertex, improving the previously best bound of $2.833n+O(1)$ due to Du et al. Our analysis is interesting on its own and involves a novel decomposition result for bipartite graphs and the introduction of an associated continuous one-dimensional bin packing instance which we can prove allows perfect packing. This question is motivated by the question of the rearrangeability of 3-stage Clos networks. In that context, the corresponding parameter n of interest in the edge coloring problem is the maximum over all vertices of the number of unit-sized bins needed to pack the weights of the incident edges. In that setting, we are able to improve the bound to $2.5480 n + o(n)$, also improving a bound of $2.5625n+O(1)$ of Du et al. We also consider the online version of this problem in which edges have to be colored as soon as they are revealed. In this context, we can show that $5n$ colors are enough. This contrasts with the best known lower bound of $3n-2$ by Tsai, Wang, and Hwang but improves upon the previous best upper bound of $5.75n$ obtained by Gao and Hwang. Additionally, we show several improved bounds for more restricted versions of the problem. These online bounds are achieved by simple and easy-to-implement algorithms, inspired by the first fit heuristic for bin packing.

We consider a generalization of edge coloring bipartite graphs in which every edge has a weight in [0,1] and the coloring of the edges must satisfy that the sum of the weights of the edges incident to a vertex v of any color must be at most 1. For unit weights, König's theorem says that the number of colors needed is exactly the maximum degree. For this generalization, we show that 2. 557 n + o(n) colors are sufficient where n is the maximum total weight adjacent to any vertex, improving the previously best bound of 2. 833n+O(1) due to Du et al. This question is motivated by the question of the rearrangeability of 3-stage Clos networks. In that context, the corresponding parameter n of interest in the edge coloring problem is the maximum over all vertices of the number of unit-sized bins needed to pack the weights of the incident edges. In that setting, we are able to improve the bound to 2. 5480 n + o(n), also improving a bound of 2. 5625n+O(1) of Du et al. Our analysis is interesting in its own and involves a novel decomposition result for bipartite graphs and the introduction of an associated continuous one-dimensional bin packing instance which we can prove allows perfect packing.