Search

Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard, which settles an open question.

Developing a biobased chemical industry that copes with the current environmental challenges relies on understanding the influence of the different stages of the value chain on economic and environmental performance. This paper investigates the use of a life cycle optimization framework to assess trade-offs between environmental and economic criteria for designing supply chains for biobased polyethylene terephthalate as a case study. A multi-objective optimization model was formulated to account for the environmental impacts (through life cycle assessment) and total costs (through life cycle costing) of the case study. High environmental priority (w = 0.9) in the design of the supply chain resulted in environmental gains (in 8 out of 9 midpoint indicators) with low increments (

This paper studies the routing of multiple commodities (shipments) through a network with the aim to minimize the total cost. To transport these commodities from their origin to their destination hub, a combination of different services can be used, including scheduled trucks (following a dedicated trajectory, similar to bus routes) and express delivery. Each commodity starts its itinerary at its origin hub and needs to arrive at its destination hub before its deadline. The following cost factors are considered in the model: a fixed cost as well as a distance-based travel cost for the scheduled truck services, a cost for express delivery between each pair of hubs based on the size of the commodity, and the inventory holding cost at each hub. We first define the problem as a mixed-integer linear program (MILP). To solve this MILP, we apply a branch-and-price algorithm that relies on column generation. In a second phase, we extend our model formulation to also deal with demand uncertainty (i.e., the size of each shipment varies) and present a two-stage, scenario-based stochastic model which we also solve using the branch-and-price algorithm. To generate the scenarios for the stochastic model, we apply Sample Average Approximation (SAA). Extensive computational experiments, including a sensitivity analysis are presented.

This paper presents an improved exact algorithm for solving the order picking problem, a special case of the planar Travelling Salesperson Problem. The algorithm heavily relies on graph reduction techniques: it removes unnecessary vertices and edges from the planar graph that are not necessary in the optimal solution. As a result, we achieve a significant increase in calculation speed and reduction in the running time. The order pickers routing problem entails collecting items from storage in response to customer requests. We use the Traveling Salesperson Problem (TSP) to optimize the routes taken by order pickers. In the literature, exact algorithms — typically based on dynamic programming — only exist for small warehouses with a small number of blocks (two), while for larger warehouse layouts mainly heuristic and metaheuristic methods are provided. The presented graph reduction method allows us to adequately solve larger — more realistic — instances in a short amount of time. Our algorithm is tested on different problem instances from the literature and its performance is compared with the current state-of-the-art. We conclude that our algorithm outperforms existing algorithms in terms of simplicity, size and calculation time.

Horizontal cooperation in logistics has gathered momentum in the last decade as a way to reach economic as well as environmental benefits. In the literature, these benefits are most often assessed by aggregating all demand and then optimizing the supply chain at the level of the coalition. However, such an approach ignores the individual preferences of the participating companies and forces them to agree on a unique coalition objective. Companies with different (potentially conflicting) preferences could improve their individual outcome by diverging from this joint solution. In order to prevent such individualistic behavior, we propose an optimization framework that explicitly accounts for the individual partners’ interests. In the models presented in this paper, all partners are allowed to specify their preferences regarding the decrease in logistical costs versus reduced CO $$_{2}$$ emissions. Consequently, all stakeholders are more likely to accept the solution, and the long-term viability of the collaboration is improved. The contribution of our work is threefold. First, we formulate a multi-partner multi-objective location-inventory model. Second, we distinguish two approaches to solve such a multi-partner multi-objective optimization problem, each focusing primarily on a single dimension. The result is a set of Pareto-optimal solutions that support the decision and negotiation process. Third, we propose and compare three different solution techniques to construct a unique solution which is fair and efficient for the coalition. Our numerical experiments not only confirm the potential of collaboration but—more importantly—also reveal valuable managerial insights on the effect of dissimilarities between partners with respect to size, geographical overlap and operational preferences.

Recent studies have concentrated on environmental and economic impacts of ships. In this regard, fuel and C O 2 emission is considered as one of the important factors for such impacts. In particular, the sailing speed of the vessels affects the fuel consumption and therefore the emission directly. In this study, we consider a speed optimization problem in inland waterway, which is characterized by stochastic waiting times at the lock caused by uncertainty in lock processing time estimations of other vessels. The objective is to minimize fuel consumption of an approaching ship, such that it traverses the river segment in a set deadline. We introduce a mathematical model for this problem and evaluate the effectiveness and attractiveness of two solution approaches: an optimal solution and a simple heuristic. This creates intuitive guidelines for skippers based on information provision to select an appropriate speed decision approach to minimize the total expected fuel consumption and C O 2 emission of inland waterway transportation.

Given a complete graph with an even number of vertices, and with each edge colored with one of two colors (say red or blue), an equitable Hamiltonian cycle is a Hamiltonian cycle that can be decomposed into two perfect matchings such that both perfect matchings have the same number of red edges. We show that, for any coloring of the edges, in any complete graph on at least 6 vertices, an equitable Hamiltonian cycle exists.

Utility companies collect usage data from meters on a regular basis. The usage data are collected automatically using radio-frequency identification (RFID) technology. Each meter transmits signals from an RFID tag that are read by a vehicle-mounted reading device within a specified distance. Routing the vehicles can be modeled by a close-enough vehicle routing problem on a street network. In practice, there is uncertainty while reading meters. The signal transmitted by an RFID tag is discontinuous, and the range that each meter can be read is different and stochastic due to weather conditions, surrounding obstacles, interference, and decreasing battery life of the RFID tags. These factors can lead to meters not being read. A vehicle has to be sent at a later time to read the missed meters, and this leads to increased costs for a utility company due to additional operational costs and overtime payments to drivers. Our aim is to address the uncertainty issues of the RFID technology by generating routes that are both cost-effective and robust (we seek to minimize the number of missed reads). We use data analytics, optimization, and Bayesian statistical models to address the uncertainty. Simulation experiments using real data show that the hierarchical Bayesian statistical model gives better results compared to other Bayesian statistical models. Utility companies can potentially integrate the results from the hierarchical Bayesian statistical model into their route generating software as a decision-support tool to produce routes that are more cost-effective and robust than the routes that they currently generate.

In the freight transportation industry, long-term contracts between logistics service providers (LSP) and shippers are common. These contracts typically contain long-term commitments related to, e.g., volume, lead time and price. The latter is mostly based on the expected cost of the transport mode that will be used for the transport of a shipment with the addition of a desired profit margin, i.e., cost-plus pricing. As these contracts apply over a longer period, e.g., a year, commitments need to be made long before the execution of the transport service itself. This long-term decision making contradicts with the fundamentals of synchromodality, which assume flexibility to change decisions with respect to route and transport mode in real time. In this research, we present an extensive numerical experiment that provides insight in the service quality characteristics, i.e., long-term commitments that have a significant impact on a LSP’s cost. In addition, interaction effects between long-term commitments of different shippers are expected, which should also be considered when analysing the cost implications. These results will serve as an input for a service-based pricing strategy for synchromodal transport. Such a strategy sets a price based on service quality characteristics of the transport, rather than the used transport mode. In this way, we aim to justify a contract price while the transport mode and route are still unknown.

The status of a vertex $v$ in a connected graph is the sum of the distances from $v$ to all other vertices. The status sequence of a connected graph is the list of the statuses of all the vertices of the graph. In this paper we investigate the status sequences of trees. Particularly, we show that it is NP-complete to decide whether there exists a tree that has a given sequence of integers as its status sequence. We also present some results about trees whose status sequences are comprised of a few distinct numbers or many distinct numbers. In this direction, we provide a partial answer to a conjecture of Shang and Lin from 2011, showing that any status injective tree is unique among trees. Finally, we investigate how orbit partitions and equitable partitions relate to the status sequence.

We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most ε h for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = p_{max}, the maximum processing time of the jobs. Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most ε⋅ p_{max}., LIPIcs, Vol. 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 42:1-42:17

We introduce a general problem about bribery in voting systems. In the $\mathcal{R}$-Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the perturbed election under the voting rule R. Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count to favour candidates. As our main result, we show that $\mathcal{R}$-Multi-Bribery is fixed-parameter tractable parameterized by the number of candidates for many natural voting rules $\mathcal{R}$, including Kemeny rule, all scoring protocols, maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves the parameterized complexity of $\mathcal{R}$-Swap Bribery for all those voting rules, thereby solving a long-standing open problem and "Challenge #2" of the "Nine Research Challenges in Computational Social Choice" by Bredereck et al. Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the uniform-cost case for all scoring protocols, the maximin rule, and Bucklin rule., Comment: extended abstract appeared in proceedings of STACS 2017

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number k c of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time n O(n) + O(n 3 log ∑ c k c ) and requires n ᶿ(n) space. An interesting feature of the Cosmadakis-Papadimitriou algorithm is its logarithmic dependence on the total length ∑ c k c of the tour, allowing the algorithm to handle instances with very long tours. The superexponential dependence on the number of cities in both the time and space complexity, however, renders the algorithm impractical for all but the narrowest range of this parameter. In this article, we improve upon the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in time 2 O(n) , i.e., single-exponential in the number of cities, using polynomial space. The space requirement of our algorithm is (essentially) the size of the output, and assuming the Exponential-Time Hypothesis (ETH), the problem cannot be solved in time 2 o(n) . Our algorithm is deterministic, and arguably both simpler and easier to analyze than the original approach of Cosmadakis and Papadimitriou. It involves an optimization over directed spanning trees and a recursive, centroid-based decomposition of trees.

Platforms create value by matching participants on alternate sides of the marketplace. Although many platforms practice one-to-one matching (e.g., Uber), others can conduct and monetize one-to-many simultaneous matches (e.g., lead-marketing platforms). Both formats involve one dimension of private information, a participant’s valuation for exclusive or shared allocation, respectively. This paper studies the problem of designing an auction format for platforms that mix the modes rather than limit to one and, therefore, involve both dimensions of information. We focus on incentive-compatible auctions (i.e., where truthful bidding is optimal) because of ease of participation and implementation. We formulate the problem to find the revenue-maximizing incentive-compatible auction as a mathematical program. Although hard to solve, the mathematical program leads to heuristic auction designs that are simple to implement, provide good revenue, and have speedy performance, all critical in practice. It also enables creation of upper bounds on the (unknown) optimal auction revenue, which are useful benchmarks for our proposed auction designs. By demonstrating a tight gap for our proposed two-dimensional reserve-price-based mechanism, we prove that it has excellent revenue performance and places low information and computational burden on the platform and participants. This paper was accepted by Chris Forman, information systems.

Fuel consumption and CO2 emission are among the main criteria to assess the environmental and economical impact of vessels on inland waterways. Both criteria, however, are directly affected by the vessels' sailing speed. In this paper, we present a mathematical programming formulation of the speed optimization problem, which aims at minimizing the aggregated fuel consumption on an inland waterway network. The network can consist of multiple river segments, connected by a set of locks, without restrictions on the configuration. To allow scalability towards realistic waterway networks, we also propose a local-search based heuristic to optimize the speed for individual vessels. We evaluate the effectiveness of the heuristic by comparing it to solving the exact mathematical programming formulation. For all computational experiments, we make use of real AIS data from a section of the Dutch river network. We observe that the heuristic is able to construct a high quality solution in realistic problem settings within reasonable amount of computation time.

This thesis investigates different optimization problems in the field of scheduling. Scheduling problems model situations in which limited resources have to be assigned to tasks over time as to minimize costs, maximize profits, balance workloads among resources or improve the efficiency of the usage of resources. The goal is to develop algorithms, which can find optimal solutions in an efficient amount of time. However, many scheduling problems turn out to be computationally difficult such that we cannot hope to accomplish this goal. To overcome this, we consider approximation algorithms, which offer a trade-off by computing solutions provably close to an optimal solution in an efficient amount of time. In this thesis both exact and approximation algorithms are studied for a variety of scheduling problems. To achieve this, this research investigates the structure and properties of optimal solutions to find solutions that are provably close.

Many applications in discrete optimization lead to hard problems. Under common assumption, it is impossible to find an algorithm that (1) is efficient, (2) finds an optimal solution on (3) every instance. At least one of these requirements needs to be sacrificed to cope with these problems. In the area of approximation algorithms, the goal is to design algorithms that efficiently find provably good solutions. Typically, for approximation algorithms, provably good implies that we bound the approximation ratio of the value of the solution to the optimal value. One important reason for studying approximation algorithms is that often even on simplified problems, they give us insights in how to design heuristics for the real problem that needs to be solved. Furthermore, having a mathematical proof for an approximation guarantee often results in a deeper understanding of the structure of the underlying problem. Unfortunately, in some cases finding a guarantee on the approximation ratio is impossible, e.g., when the optimal solution value is 0. Or the approximation guarantee is overly pessimistic, e.g., Graham’s (1966) seminal List Scheduling algorithm for makespan scheduling is guaranteed to find a solution with value at most twice the optimal value, but when processing times are small List Scheduling performs much better. To overcome these issues, we consider the concept of additive approximation algorithms. Instead of bounding the ratio, in additive approximation we bound the absolute difference between the value of the solution of the approximation algorithm and the optimal solution value. We apply the concept of additive approximation and additive approximation schemes, that can get arbitrarily close to an optimal solution, for several load balancing problems.

The classic prophet inequality states that, when faced with a finite sequence of nonnegative independent random variables, a gambler who knows the distribution and is allowed to stop the sequence at any time, can obtain, in expectation, at least half as much reward as a prophet who knows the values of each random variable and can choose the largest one. In this work, we consider the situation in which the sequence comes in random order. We look at both a nonadaptive and an adaptive version of the problem. In the former case, the gambler sets a threshold for every random variable a priori, whereas, in the latter case, the thresholds are set when a random variable arrives. For the nonadaptive case, we obtain an algorithm achieving an expected reward within at least a 0.632 fraction of the expected maximum and prove that this constant is optimal. For the adaptive case with independent and identically distributed random variables, we obtain a tight 0.745-approximation, solving a problem posed by Hill and Kertz in 1982. We also apply these prophet inequalities to posted price mechanisms, and we prove the same tight bounds for both a nonadaptive and an adaptive posted price mechanism when buyers arrive in random order.

We consider decision problems with arbitrary action spaces, deterministic transitions, and infinite time horizon. In the usual setup when probability measures are countably additive, a general version of Kuhn’s theorem implies under fairly general conditions that for every mixed strategy of the decision maker there exists an equivalent behavior strategy. We examine to what extent this remains valid when probability measures are only assumed to be finitely additive. Under the classical approach of Dubins and Savage (2014), we prove the following statements: (1) If the action space is finite, every mixed strategy has an equivalent behavior strategy. (2) Even if the action space is infinite, at least one optimal mixed strategy has an equivalent behavior strategy. The approach by Dubins and Savage turns out to be essentially maximal: these two statements are no longer valid if we take any extension of their approach that considers all singleton plays.

The estate division problem considers the issue of dividing an estate when the sum of entitlements is larger than the estate. This paper studies the estate division problem from a noncooperative perspective. The integer claim game introduced by O'Neill (1982) and extended by Atlamaz et al. (2011) is generalized by specifying a sharing rule to divide every interval among the claimants. We show that for all problems for which the sum of entitlements is at most twice the estate the existence of a Nash equilibrium is guaranteed for a general class of sharing rules. Moreover, the corresponding set of equilibrium payoffs is independent of which sharing rule in the class is used. Well-known division rules that always assign a payoff vector in this set of equilibrium payoffs are the adjusted proportional rule, the random arrival rule and the Talmud rule.

We examine the guarantee levels of the players in a type of zero sum games. We show how these levels depend on the sigma algebras that are being employed on the players' action spaces. We further argue that guarantee levels may therefore also depend on set theoretic considerations. Additionally, we calculate the guarantee levels for finitely additive strategies. The solutions of catch games essentially differ among these setups. We find optimal strategies for almost all cases.

The classic prophet inequality states that, when faced with a finite sequence of non-negative independent random variables, a gambler who knows their distribution and is allowed to stop the sequence at any time, can obtain, in expectation, at least half as much reward as a prophet who knows the values of each random variable and can choose the largest one. Following this classic theorem from the 70s, many results have been obtained for several related optimal stopping problems. Moreover, the recently uncovered connection between prophet inequalities and posted price mechanisms, has given the area a new surge. We survey some new developments and highlight some compelling open problems.

In second-price auctions with interdependent values, bidders do not necessarily have dominant strategies. Moreover, such auctions may have many equilibria. In order to rule out the less intuitive equilibria, we define the notion of distributional strictly perfect equilibrium (DSPE) for Bayesian games with infinite type and action spaces. This equilibrium is robust against arbitrary small perturbations of strategies. We apply DSPE to a class of symmetric second-price auctions with interdependent values. We show that the efficient equilibrium defined by Milgrom (1981) is a DSPE, while a class of less intuitive, inefficient, equilibria introduced by Birulin (2003) is not.

In this paper a general solution framework is presented for optimising decisions in a horizontal logistics cooperation. The framework distinguishes between the objective of the group and the objectives of the individual partners in the coalition. Although the importance of the individual partner interests is often acknowledged in the literature, the proposed solution framework is the first to include these objectives directly into the objective function of the optimisation model. The solution framework is applied to a collaborative variant of the clustered vehicle routing problem, for which we also create a set of benchmark instances. We find that by only considering a global coalition objective, the obtained solution is often suboptimal for some partners in the coalition. Providing a set of high quality alternative solutions that are Pareto efficient with respect to the partner objectives, gives additional insight in the sensitivity of a solution, which can support the decision making process. Our computational results therefore acknowledge the importance of including the individual partner objectives into the optimisation procedure. (C) 2017 Elsevier Ltd. All rights reserved.

Machine scheduling problems are a long-time key domain of algorithms and complexity research. A novel approach to machine scheduling problems are fixed-parameter algorithms. To stimulate this thriving research direction, we propose 15 open questions in this area whose resolution we expect to lead to the discovery of new approaches and techniques both in scheduling and parameterized complexity theory., Comment: Version accepted to Computers & Operations Research

This paper is dealing with the order picker routing problem within a multi-block warehouse layout with several aisles. In the literature, exact algorithms only exist for small warehouses with few cross aisles (typically two or three), while for larger warehouse configurations a series of heuristic and meta-heuristic methods are available. We present a novel pre-processing algorithm for graph reduction by eliminating the extra corner vertices and aisles from the graph of warehouse locations and aisles. This allows us to solve this routing problem with a general TSP solver while significantly reducing running times. The presented method allows us to solve adequately big (more realistic) instances exactly. The algorithm is implemented and evaluated experimentally on a set of problem instances from the literature. The computational results illustrate that the proposed model outperforms existing formulations in terms of simplicity, size, and calculation time. Our mathematical model gives an optimum solution for all the instances, while the network size could be reduced by almost 73% on average.

Order picking describes the process of retrieving a set of products from a warehouse in response to newly incoming customer orders. Deterministic order picking models assume all customer orders to be known at the beginning of the planning horizon. As a result, the application of such models in a dynamic environment is limited to a reactive strategy and ad-hoc decision-making each time new information becomes available. To mitigate demand uncertainty and improve the efficiency of the picking operations, we explore the idea of anticipatory order picking (AOP). In AOP, expected (but uncertain) customer orders are considered when planning and executing order picking activities. In contrast to the confirmed orders, these expected orders - if picked - are stored in a small buffer zone close to the packing and/or labeling station from which they can be retrieved with very limited travel time. Extensive simulation experiments revealed the following advantages. First, AOP can provide a better workload balance by relocating peak hour orders during preceding, off-peak time intervals. Second, by picking orders at a time when their marginal travel cost is low, the total travel time and distance are reduced as well as the overall amount of traffic in the warehouse. Third, by better utilizing the pickers’ working time, the picking of all confirmed orders can complete earlier.

In empirical studies, practitioners routinely adopt linear models as approximations to complicated economic relations. Linear models are helpful in substantive economic problems. Ignoring nonlinear features, however, can sometimes be misleading for policymakers. To understand the complexity of the real world, simple, interpretable nonlinear models are advantageous. To this end, this research have developed multiple statistical methods for time series data with nonlinearity and non-stationarity. The study mainly considered two sets of models. The first set is called trend-break models that allow a structural break in the time trend, possibly due to changes in policy or external events, without the information of break dates to modelers. The dissertation proposes a framework to pin down the break dates and quantify the estimation uncertainty. The second set is the co-integrating polynomial regression models. It is motivated mainly by the environmental Kuznets curve hypothesis that postulates an inverse U-shaped relationship between per capita income and environmental degradation. The study offers some statistical methods to assess this hypothesis carefully.

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.

In the transport industry, long term contracts between shippers and logistics service providers are common. These contracts typically contain commitments related to volume, lead time and price. As these contracts run over a longer period (e.g., a year), these commitments are made long before the execution of the transport service itself. Synchromodal transportation, however, is founded on the idea of having the flexibility to change decisions with respect to, e.g., route and transport mode in real time, which leads to challenges to make the typical commitments long in advance. In this research, we study pricing strategies from a network flow perspective. More specifically, we focus on the impact of this mix of long-term commitments (contracts) and ad-hoc shipping on network planning and pricing.

In stochastic online scheduling problems, a common class of policies is the class of fixed assignment policies. These policies first assign jobs to machines and then apply single machine scheduling policies for each machine separately. We consider a stochastic online scheduling problem for which the goal is to minimize total weighted expected completion time on uniform parallel machines. To solve the problem, we adapt policies introduced for the identical and unrelated parallel machine environments. We show that, with the help of lower bounds specific for the uniform machine environment, we can tighten the performance guarantees that are implied by the results for the unrelated machine environment for the special case of two machine speeds. Furthermore, in the Online-List model we show that a greedy assignment policy is asymptotically optimal. Finally, we construct a computational study to assess the performance of the policies in practice.

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.

We present a general model for the operation of a cloud computing server comprised of one or more speed-scalable processors. Typically, tasks are submitted to such a cloud computing server in an online fashion, and the server operator has to schedule the tasks and decides on payments without knowledge about the tasks arriving in the future. Although very natural, this cloud computing problem on speed-scalable processors has not been studied from a mechanism design perspective in the online setting. We provide a mechanism for this setting, both for a single and multiprocessor environment, that has several desirable properties: (1) the induced game admits a subgame perfect equilibrium in pure strategies and therefore a pure Nash equilibrium, (2) the Price of Anarchy is constant, (3) the mechanism is budget balanced, i.e., the sum of the payments of the agents is equal to the total energy costs, (4) the communication complexity is low, (5) the mechanism is computationally tractable for both the service operator and the agents, and (6) the agents' payment is also intuitive and easy to communicate to them. We also provide a second mechanism with a better Price of Anarchy, which in turn is more involved to implement. We are able to extend our mechanisms and results to the Bayesian setting, where the type of each agent is drawn independently from some underlying distribution and agents are minimizing their expected costs. In this setting we also show the same approximation factor of our mechanism as in the basic online setting in both the single and the multiprocessor environment.

We study the role of direct and indirect incentives, as well as accounting/feedback systems, in a system of dynamic favour exchange. Subjects are placed in small groups and each period are further matched in subgroups of two where one player (the sender) exerts costly effort, which generates a benefit for his/her match (the receiver). That is, she does a favour. Senders exert substantial costly effort on behalf of receivers, even when no direct incentives are in place. However we show that when direct monetary incentives are in place (receivers pay senders for their effort in points, and points are converted to money at the end of the experiment), it leads to higher average efficiency and less variability of behavior. In the absence of direct incentives, with or without a public accounting system, group behavior is markedly different between those groups that score highly on the social value orientation (SVO) and those that do not. High SVO groups are able to meet or exceed the efficiency level achieved under direct incentives. When direct incentives are present, there is no difference between high and low SVO groups; instead play converges to the subgame perfect Nash equilibrium based on selfish preferences. (C) 2020 Elsevier B.V. All rights reserved.

Optimal dike heights are of crucial importance to the Netherlands as almost 60% of its surface is under threat of flooding from sea, lakes, or rivers. This area is protected by more than 3500 kilometres of dunes and dikes. These dunes and dikes require substantial annual investments of over 1 billion euro. In this paper we propose an integer programming model for a cost-benefit analysis to determine optimal dike heights. We improve upon the model proposed by Brekelmans, den Hertog, Roos and Eijgenraam (2012). Our model provides an alternative approach with almost complete flexibility towards input-parameters for flood probabilities, damage costs and investment costs for dike heightening. We present an easy-to-implement algorithm that provides an optimal solution to the problem. The method has been implemented and tested for the most recent data on flood probabilities, damage and investment costs, which were recently used by the government to determine the new safety standards in the Dutch Water Act.

We study a variation of hotelling’s location model in which consumers choose between firms based on travel distances as well as the number of consumers visiting each firm. The model in which the network externality is the same for all firms was proposed by kohlberg (econ lett 11:211–216, 1983), who claims that no equilibrium exists for more than two firms. We assume the network effects to be linear and, in contrast to the claim in kohlberg (econ lett 11:211–216, 1983), derive a condition under which a subgame perfect nash equilibrium exists for four and six firms. Moreover, we show that for more than two firms the equilibrium locations of the firms are different from the equilibrium locations in hotelling’s location model. Our results suggest that a subgame perfect nash equilibrium exists if and only if the number of firms is even. We also provide examples of subgame perfect equilibria in which the network externality is different for some of the firms.

Using a network approach we provide a characterization of a separating equilibrium for standard signaling games where the sender's payoff function is quasi-linear. Given a strategy of the sender, we construct a network where the node set and the length between two nodes are the set of the sender's type and the difference of signaling costs, respectively. Construction of a separating equilibrium is then equivalent to constructing the length between two nodes in the network under the condition that the response of the receiver is a node potential. When the set of the sender's type is a real interval, shortest path lengths are antisymmetric and a node potential is unique up to a constant. A strategy of the sender in a separating equilibrium is characterized by some differential equation with a unique solution. Our results can be readily applied to a broad range of economic situations, such as for example the standard job market signaling model of Spence, a model not captured by earlier papers.

The second-largest eigenvalue and second-smallest Laplacian eigenvalue of a graph are measures of its connectivity. These eigenvalues can be used to analyze the robustness, resilience, and synchronizability of networks, and are related to connectivity attributes such as the vertex- and edge-connectivity, isoperimetric number, and characteristic path length. In this paper, we present two upper bounds for the second-largest eigenvalues of regular graphs and multigraphs of a given order which guarantee a desired vertex- or edge-connectivity. The given bounds are in terms of the order and degree of the graphs, and hold with equality for infinite families of graphs. These results answer a question of Mohar., 24 pages

The conjecture of Graham and Lov ́asz that the (normalized) coefficients of the distance characteristic polynomial of a tree are unimodal is proved; it is also shown that the (normalized) coefficients are log-concave. Upper and lower bounds on the location of the peak are established.

We consider the joint decision of placing public bads in each of two neighboring countries, modeled by two adjacent line segments. Residents of the two countries have single-dipped preferences, determined by the distance of their dips to the nearer public bad (myopic preferences) or, lexicographically, by the distance to the nearer and the other public bad (lexmin preferences). A (social choice) rule takes a profile of reported preferences as input and assigns the location of the public bad in each country. For the case of myopic preferences, all rules satisfying strategy-proofness, country-wise Pareto optimality, non-corruptibility, and the far away condition are characterized. These rules pick only border locations. The same holds for lexmin preferences under strategy-proofness and country-wise Pareto optimality alone. (C) 2016 Elsevier B.V. All rights reserved.