BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Wieslaw Kubiak

Wieslaw Kubiak contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Discrete MathematicsData Structures and Algorithmsmath.COComputational Complexity

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

6 published item(s)

preprint2022arXiv

On the complexity of open shop scheduling with time lags

The minimization of makespan in open shop with time lags has been shown NP-hard in the strong sense even for the case of two machines and unit-time operations. The minimization of total completion time however has remained open for that case though it has been shown NP-hard in the strong sense for weighted total completion time or for jobs with release dates. This note shows that the minimization of total completion time for two machines and unit-time operations is NP-hard in the strong sense which answers the long standing open question.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On a Conjecture for a Hypergraph Edge Coloring Problem

Let $H =(\mathcal{M} \cup \mathcal{J} ,E \cup \mathcal{E})$ be a hypergraph with two hypervertices $\mathcal{G}_1$ and $\mathcal{G}_2$ where $\mathcal{M} =\mathcal{G}_{1} \cup \mathcal{G}_{2}$ and $\mathcal{G}_{1} \cap \mathcal{G}_{2} =\varnothing $. An edge $\{h ,j\} \in E$ in a bi-partite multigraph graph $(\mathcal{M} \cup \mathcal{J} ,E)$ has an integer multiplicity $b_{j h}$, and a hyperedge $\{\mathcal{G}_{\ell } ,j\} \in \mathcal{E}$, $\ell=1,2$, has an integer multiplicity $a_{j \ell }$. It has been conjectured in [5] that $χ\prime (H) =\lceil χ\prime _{f} (H)\rceil $, where $χ\prime (H)$ and $χ\prime _{f} (H)$ are the edge chromatic number of $H$ and the fractional edge chromatic number of $H$ respectively. Motivation to study this hyperedge coloring conjecture comes from the University timetabling, and open shop scheduling with multiprocessors. We prove this conjecture in this paper.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Shared multi-processor scheduling

We study shared multi-processor scheduling problem where each job can be executed on its private processor and simultaneously on one of many processors shared by all jobs in order to reduce the job's completion time due to processing time overlap. The total weighted overlap of all jobs is to be maximized. The problem models subcontracting scheduling in supply chains and divisible load scheduling in computing. We show that synchronized schedules that complete each job at the same time on its private processor and shared processors, if any is actually used by the job, include optimal schedules. We prove that the problem is NP-hard in the strong sense for jobs with arbitrary weights, and we give an efficient, polynomial-time algorithm for the problem with equal weights.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Shared processor scheduling

We study the shared processor scheduling problem with a single shared processor where a unit time saving (weight) obtained by processing a job on the shared processor depends on the job. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an $O(n \log n)$ optimization algorithm for a class of instances in which non-decreasing order of jobs with respect to processing times provides a non-increasing order with respect to weights --- this instance generalizes the unweighted case of the problem. This algorithm also leads to a $\frac{1}{2}$-approximation algorithm for the general weighted problem. The complexity of the weighted problem remains open.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Structural Properties of an Open Problem in Preemptive Scheduling

Structural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on `shifts', i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. So far only rough bounds for these parameters have been derived for specific problems. This paper sharpens the bounds on these structural parameters for a well-known open problem in the theory of preemptive scheduling: Instances consist of in-trees of $n$ unit-execution-time jobs with release dates, and the objective is to minimize the total completion time on two processors. This is among the current, tantalizing `threshold' problems of scheduling theory: Our literature survey reveals that any significant generalization leads to an NP-hard problem, but that any significant simplification leads to tractable problem. For the above problem, we show that the number of preemptions necessary for optimality need not exceed $2n-1$; that the number must be of order $Ω(\log n)$ for some instances; and that the minimum shift need not be less than $2^{-2n+1}$. These bounds are obtained by combinatorial analysis of optimal schedules rather than by the analysis of polytope corners for linear-program formulations, an approach to be found in earlier papers. The bounds immediately follow from a fundamental structural property called `normality', by which minimal shifts of a job are exponentially decreasing functions. In particular, the first interval between a preempted job's start and its preemption is a multiple of 1/2, the second such interval is a multiple of 1/4, and in general, the $i$-th preemption occurs at a multiple of $2^{-i}$. We expect the new structural properties to play a prominent role in finally settling a vexing, still-open question of complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Minimum length path decompositions

We consider a bi-criteria generalization of the pathwidth problem, where, for given integers $k,l$ and a graph $G$, we ask whether there exists a path decomposition $\cP$ of $G$ such that the width of $\cP$ is at most $k$ and the number of bags in $\cP$, i.e., the \emph{length} of $\cP$, is at most $l$. We provide a complete complexity classification of the problem in terms of $k$ and $l$ for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to $k$, we prove that the generalized problem is NP-complete for any fixed $k\geq 4$, and is also NP-complete for any fixed $l\geq 2$. On the other hand, we give a polynomial-time algorithm that, for any (possibly disconnected) graph $G$ and integers $k\leq 3$ and $l>0$, constructs a path decomposition of width at most $k$ and length at most $l$, if any exists. As a by-product, we obtain an almost complete classification of the problem in terms of $k$ and $l$ for connected graphs. Namely, the problem is NP-complete for any fixed $k\geq 5$ and it is polynomial-time for any $k\leq 3$. This leaves open the case $k=4$ for connected graphs.

0 citations0 reviewsNo code linkedOpen access