BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Vincent J. C. Kreuzen

Vincent J. C. Kreuzen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryDiscrete Mathematicsmath.COmath.OC

Catalog footprint

What is connected

3works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

3 published item(s)

preprint2015arXiv

High Multiplicity Scheduling with Switching Costs for few Products

We study a variant of the single machine capacitated lot-sizing problem with sequence-dependent setup costs and product-dependent inventory costs. We are given a single machine and a set of products associated with a constant demand rate, maximum loading rate and holding costs per time unit. Switching production from one product to another incurs sequencing costs based on the two products. In this work, we show that by considering the high multiplicity setting and switching costs, even trivial cases of the corresponding "normal" counterparts become non-trivial in terms of size and complexity. We present solutions for one and two products.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Characterizing width two for variants of treewidth

In this paper, we consider the notion of \emph{special treewidth}, recently introduced by Courcelle\cite{Courcelle2012}. In a special tree decomposition, for each vertex $v$ in a given graph, the bags containing $v$ form a rooted path. We show that the class of graphs of special treewidth at most two is closed under taking minors, and give the complete list of the six minor obstructions. As an intermediate result, we prove that every connected graph of special treewidth at most two can be constructed by arranging blocks of special treewidth at most two in a specific tree-like fashion. Inspired from the notion of special treewidth, we introduce three natural variants of treewidth, namely \emph{spaghetti treewidth}, \emph{strongly chordal treewidth} and \emph{directed spaghetti treewidth}. All these parameters lie between pathwidth and treewidth, and we provide common structural properties on these parameters. For each parameter, we prove that the class of graphs having the parameter at most two is minor closed, and we characterize those classes in terms of a \emph{tree of cycles} with additional conditions. Finally, we show that for each $k\geq 3$, the class of graphs with special treewidth, spaghetti treewidth, directed spaghetti treewidth, or strongly chordal treewidth, respectively at most $k$, is not closed under taking minors.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fare Evasion in Transit Networks

Public transit systems in urban areas usually require large state subsidies, primarily due to high fare evasion rates. In this paper, we study new models for optimizing fare inspection strategies in transit networks based on bilevel programming. In the first level, the leader (the network operator) determines probabilities for inspecting passengers at different locations, while in the second level, the followers (the fare-evading passengers) respond by optimizing their routes given the inspection probabilities and travel times. To model the followers' behavior we study both a non-adaptive variant, in which passengers select a path a priori and continue along it throughout their journey, and an adaptive variant, in which they gain information along the way and use it to update their route. For these problems, which are interesting in their own right, we design exact and approximation algorithms and we prove a tight bound of 3/4 on the ratio of the optimal cost between adaptive and non-adaptive strategies. For the leader's optimization problem, we study a fixed-fare and a flexible-fare variant, where ticket prices may or may not be set at the operator's will. For the latter variant, we design an LP based approximation algorithm. Finally, using a local search procedure that shifts inspection probabilities within an initially determined support set, we perform an extensive computational study for all variants of the problem on instances of the Dutch railway and the Amsterdam subway network. This study reveals that our solutions are within 95% of theoretical upper bounds drawn from the LP relaxation.

0 citations0 reviewsNo code linkedOpen access